h_sh
June 21, 2020, 7:30pm
35
Why this code is giving TLE?
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<bitset>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 1000000
double income[N],pop[N];
double ans =0;
ll vis[N];
ll size;
vector<ll> final;
void dfs(vector<vector<ll>> a,ll c,)
{
vis[c]=1;
for(ll i=0;i<a[c].size();i++)
{
if(vis[a[c][i]]==0)
{
dfs(a,a[c][i]);
}
}
}
main()
{
ll t;
cin>>t;
while(t--)
{
ll n,m;
cin>>n>>m;
vector<vector<ll>> a(n,vector<ll>());
for(ll i=0;i<n;i++)cin>>income[i];
for(ll i=0;i<n;i++)cin>>pop[i];
for(ll i=0;i<m;i++)
{
ll u,v;
cin>>u>>v;
u--;
v--;
a[u].push_back(v);
a[v].push_back(u);
}
double avg[n];
vector<pair<double,ll> >vx;
double mv =0;
ll ind;
for(ll i=0;i<n;i++)
{
avg[i] = (double)income[i]/(double)pop[i];
// vx.push_back({avg[i],i});
if(mv<avg[i])
{
mv=avg[i];
ind=i;
}
}
vector<ll> possible;
possible.push_back(ind);
for(ll i=0;i<n;i++)
{
if(i==ind)
continue;
if(fabs(avg[i]-avg[ind])<0.0000001f)
{
// cout<<i<<"add"<<endl;
possible.push_back(i);
}
}
if(possible.size()==1)
{
cout<<mv<<endl;
cout<<possible[0]+1<<endl;
continue;
}
for(ll i=0;i<n;i++)
vis[i]=0;
vis[ind]=1;
dfs(a,avg[ind],ind,n,vector<ll>());
cout<<mv<<endl;
for(ll i=0;i<possible.size();i++)
{
if(vis[possible[i]]==1)
cout<<possible[i]+1<<" ";
}
cout<<endl;
}
}
h_sh
June 21, 2020, 7:41pm
36
MOdify by eleminating some extra logic but still it giving TLE
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<bitset>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 1000000
double income[N],pop[N];
double ans =0;
ll vis[N];
ll cc[N];
ll size;
vector<ll> final;
void dfs(vector<vector<ll>> a,ll c)
{
vis[c]=1;
for(ll i=0;i<a[c].size();i++)
{
if(vis[a[c][i]]==0 && cc[a[c][i]]==1 )
{
dfs(a,a[c][i]);
}
}
}
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n,m;
cin>>n>>m;
vector<vector<ll>> a(n,vector<ll>());
for(ll i=0;i<n;i++)cin>>income[i];
for(ll i=0;i<n;i++)cin>>pop[i];
for(ll i=0;i<m;i++)
{
ll u,v;
cin>>u>>v;
u--;
v--;
a[u].push_back(v);
a[v].push_back(u);
}
double avg[n];
double mv =0;
ll ind;
for(ll i=0;i<n;i++)
{
avg[i] = (double)income[i]/(double)pop[i];
cc[i]=0;
if(mv<avg[i])
{
mv=avg[i];
ind=i;
}
}
ll possible=1;
for(ll i=0;i<n;i++)
{
if(i==ind)
continue;
if(fabs(avg[i]-avg[ind])<0.0000001f)
{
cc[i]=1;
possible++;
}
}
if(possible==1)
{
cout<<mv<<endl;
cout<<ind+1<<endl;
continue;
}
for(ll i=0;i<n;i++)
vis[i]=0;
vis[ind]=1;
dfs(a,ind);
cout<<mv<<endl;
for(ll i=0;i<n;i++)
{
if(vis[i]==1)
cout<<i+1<<" ";
}
cout<<endl;
}
return 0;
}
@taran_1407 @rezwanarefin01 @raja1999
Looks like you have used some sets. My dfs passed within limits.
Done exactly as stated by @taran_1407 orz.
https://www.codechef.com/viewsolution/34622915
2 Likes
DFS approach AC C++. Really good problem. My submission
I agree…I need to shift to cpp now.
1 Like
Definitely you should brother. Python may seem very handy for easy, easy-medium questions, but when it comes to strict time-limits and long implementations, there’s no beating C++.
2 Likes
Codechef stills give 5X for Python (though Python may TLE within that range as well) but Codeforces doesn’t give any multiplier to Python. Secondly, implementation of most of the tough topics is only given in cpp and as always cpp is fast. So, you’re right.
Actually, the time multiplier for PYPY is 2, but for Pyhton 3. it’s 5. That’s why you got accepted submitting in Pyhton 3 but not in PYPY.
But PyPy is faster than Python. So, that is why Multiplier of PyPy is less. My Solution in PyPy gave TLE during the contest and got accepted in Python. Now the same solution after the contest is giving AC in both.
Can someone explain me this test-case ?
1
4 4
10 1 2 100000000
5 1 1 1
1 2
2 3
1 3
2 4
We are not considering 2nd node as explained above but if I considered 2nd node then I can consider 4th node as well and it will increase per capita income
Not considering 2nd node:
Considering 2nd and 4th node:
Clearly, Y > X
@taran_1407 @rezwanarefin01 @raja1999
Why don’t you consider 100000000/1 ??
2 Likes
Can someone help. I did exactly the same thing as the editorial. Used BFS approach. Here is my solution.
I got wa when I used double and got ac by using long double
That’s nice. But sometimes you can lose precision even with long double. So it’s always best to use integer comparison if it’s possible.
You must have done something else wrong, because I got AC on double.
even i also applied the same approach ,but getting TLE.I also tried implementing using scanf and printf for i/o but still getting TLE
