Yeah i got it Brother.Later On, i read this line:
“there is atmost one road between each pair of provinces”
In place of “atmost” if it would be written “atleast” then i think my approach would be right.
Thanks a lot
1 Like
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
#define pb push_back
#define ll long long
vector<vector<int>> components;
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].pb(v);
adj[v].pb(u);
}
vector<bool> used;
vector<int> city;
void dfs(vector<int> adj[], vector<int> cities, int u)
{
if(used[u] || !binary_search(cities.begin(), cities.end(), u)) return;
used[u] = true;
city.pb(u);
for(int v : adj[u])
{
dfs(adj, cities, v);
}
}
int main()
{
FASTIO
int t;
cin >> t;
while(t--)
{
int n, m;
cin >> n >> m;
components.clear();
used.assign(n, false);
vector<ll> a(n), b(n);
rep(i,0,n) cin >> a[i];
rep(i,0,n) cin >> b[i];
vector<int> adj[n];
rep(i,0,m)
{
int u, v;
cin >> u >> v;
addEdge(adj, u-1, v-1);
}
//Finding max per-capita income
ll num = a[0], den = b[0];
rep(i,1,n)
{
if(a[i]*den > b[i]*num)
{
num = a[i];
den = b[i];
}
}
//Marking all the nodes with the maximum per-capita income
vector<int> cities;
rep(i,0,n)
{
if(a[i]*den == b[i]*num) cities.pb(i);
}
// for(int x : cities) cout << x << " ";
// cout << "\n";
for(int u : cities)
{
if(!used[u])
{
dfs(adj, cities, u);
components.pb(city);
}
city.clear();
}
// for(auto x : components)
// {
// for(auto y : x) cout << y << " ";
// cout << "\n";
// }
//Finding the largest component
int max_len = 0;
rep(i,0,components.size())
{
if(components[i].size() > components[max_len].size())
max_len = i;
}
cout << components[max_len].size() << "\n";
for(auto k : components[max_len]) cout << k+1 << " ";
cout << "\n";
}
return 0;
}
Can anyone please help me eliminate TLE? And is my code correct?
You are passing the adjacency list and also the cities by value. So each time you call the function a copy of the vector is made and, that’s an additional O(n), where n is the vector size. It’s good to pass it by reference, and even better to just have these as global vectors. Your accepted solution is here.
1 Like
The video editorial for this problem is here:
Checkout codechef cook off problem - per capita income detailed explanation
1 Like
Because of precision issues.
Refer this
You can avoid this by not dividing and working only with integers by cross multiplication.
this solution is giving RE but working fine with sample input and some random inputs i used for testing .
I tried asking this in several threads of codechef discussion but haven’t received any feedback.
really worried…please help me out guys … @aneesh2312 @dark_horse07 @sebastian @robosapien @ameybhavsar @dark_horse07
import collections
def dfs(p):
visited.add(p)
temp.add(p+1)
for node in road[p]:
if(node not in visited and selected[node]):
dfs(node)
t=int(input())
for _ in range(t):
n,m=map(int,input().split())
income=list(map(int,input().split()))
pop=list(map(int,input().split()))
road=collections.defaultdict(list)
for __ in range(m):
a,b=map(int,input().split())
road[a-1].append(b-1)
road[b-1].append(a-1)
i=income[0]
p=pop[0]
# to find max per capita
for x in range(1,n):
if(i*pop[x]<p*income[x]):
i=income[x]
p=pop[x]
selected=[False]*n
# to select node with max per capita
for x in range(n):
if(pop[x]*i== income[x]*p):
selected[x]=True
visited=set()
ans=set()
for each in range(n):
if(each not in visited and selected[each]):
temp=set()
dfs(each)
if(len(temp)>len(ans)):
ans=temp
print(len(ans))
print(*ans)Bro, I don’t know much about python. I don’t know why this is giving RE
can u provide some test cases so that can i can debug please …
i am new don’t how to generate it.
it will be kind if you tag someone who knows python and can help me out ?
please please…
Thanks! It helped.
1 Like
I am getting WA . Even after thinking for hours I can’t spot the mistake. Please help.
Here’s my solution CodeChef: Practical coding for everyone
You certainly have overflow while comparing ar1[i]*e > ar2[i]*w, use long long datatype.
1 Like
Thank you so much sir !
Now i can happily end the day after getting that green tick.
Thanks again for helping noobs like me.
1 Like
CodeChef: Practical coding for everyone still not getting accepted… even after using scanf and printf
Friends I am getting TLE. could someone help me please.