It’s because you are using a set to keep track of nodes. A simple vector should be enough as we do not care about the order. Insertion time for a set is O(\text{log }n). Generally, it should be fine but this problem seems to have pretty tight constraints.
My Submission
BFS implementation
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
long long int a[n+1],b[n+1];
int i;
vectoradj[n+1];
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
cin>>b[i];
for(i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
long long int num=a[1],deno=b[1];
int vis[n+1]={0};
vectorv[n+1];
for(i=2;i<=n;i++)
{
if(a[i]*deno>b[i]*num)
{
num=a[i];
deno=b[i];
}
}
int max=0;
for(i=1;i<=n;i++)
{
if(a[i]*deno==b[i]*num&&vis[i]==0)
{
queueq;
q.push(i);
vis[i]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
v[i].push_back(x);
for(auto j:adj[x])
{
if(a[j]*deno==b[j]*num&&vis[j]==0)
{
vis[j]=1;
q.push(j);
}
}
}
if(v[i].size()>v[max].size())
max=i;
}
}
cout<<v[max].size()<<endl;
sort(v[max].begin(),v[max].end());
for(auto j: v[max])
cout<<j<<" ";
cout<<endl;
}
return 0;
}
using same concept, with dfs and fast io still getting tle
the king would prefer the number of chosen provinces to be as large as possible.
I somehow thought we had to maximize the population. The DSU tag made me realize. 
I wonder why every problem’s Difficulty is tagged as easy.We can say easy to A B problems but ‘C’ problem comes under Div1.
I went through the exact same train of thought. I was not even able to submit one question during the contest because of that! 
.
Easy problems in codechef doesn’t mean very easy. Very easy problems are tagged as beginner and cakewalk I guess. I generally relate to codechef easy problems as easy-medium.
And this problem is actually very easy if you have the knowledge of DSU. implementation with dfs and bfs is not very easy.
Sample case was passing so i had no idea where i was going wrong.
1 Like
Damn. You implemented that? I was stuck and couldn’t think of an algorithm for the misunderstood question. So I never had a chance to test the sample input :3.
Probably wrong implementation i’m guessing now.
1 Like
Could you tell how after making a graph with all the nodes can we discard some nodes and keep the remaining nodes?
Please reply.
wrong ans even though my logic is same just like editorial,can anyone please help me?
https://www.codechef.com/viewsolution/34604725
https://www.codechef.com/viewsolution/34650702
I replaced cout/cin with printf/scanf and it got accepted , it should be looked too.
I Haven’t used DSU or DFS to Solve this problem.
I am only finding the maximum percapita income and if that max. percapita income are multiple , i am only considering all of them and just printing them in my solution.
But with this approach i am Getting WA.
My Solution-Click Here
Can Anybody Tell me where i am going wrong?
The regions must be connected. There might be disconnected regions if you do it like that.
Why is my code getting WA? Can someone help me?
#include <bits/stdc++.h>
#include <chrono>
#define ll long long int
#define ull usigned long long int
#define pb push_back
#define FASTIO cin.tie(0); ios_base::sync_with_stdio(false)
using namespace std;
const int MOD = 1e9 + 7;
const int maxN = 2e5 + 10;
struct Timer{
chrono::high_resolution_clock::time_point start, end;
chrono::duration<double> duration;
Timer(){
start = chrono::high_resolution_clock::now();
}
~Timer(){
end = chrono::high_resolution_clock::now();
duration = end - start;
cout << "Time : " << duration.count() << "s\n";
}
};
ll gcd(ll a, ll b){
if(a == 0){
return b;
}
return gcd(b % a, a);
}
ll powx(ll n, ll p){
ll res = 1;
while(p){
if(p & 1){
res = (res * n) % MOD;
--p;
}
else{
n = (n * n) % MOD;
p /= 2;
}
}
return res;
}
bool myswap(const pair<float, int> a, const pair<float, int> b){
if(a.first == b.first){
return a.second < b.second;
}
return (a.first > b.first);
}
bool visited[maxN + 1];
vector <int> adj[maxN + 1];
vector <int> idx;
bool choose[maxN + 1];
vector <int> temp, ans;
void init(){
memset(visited, 0, sizeof(visited));
memset(choose, 0, sizeof(choose));
idx.clear();
temp.clear();
ans.clear();
}
void dfs(int u){
for(int i = 0; i < adj[u].size(); ++i){
if(!visited[adj[u][i]] && choose[adj[u][i]]){
visited[adj[u][i]] = 1;
temp.pb(adj[u][i]);
dfs(adj[u][i]);
}
}
}
void solver(){
init();
int n, m, u, v;
cin >> n >> m;
float a[n], b[n];
vector <pair<float, int>> p;
for(int i = 0; i < n; ++i){
scanf(" %f", a + i);
}
for(int i = 0; i < n; ++i){
scanf(" %f", b + i);
p.pb({a[i]/b[i], i + 1});
}
for(int i = 0; i < m; ++i){
scanf(" %d %d", &u, &v);
adj[u].pb(v);
adj[v].pb(u);
}
sort(p.begin(), p.end(), myswap);
float max_v = p[0].first;
idx.pb(p[0].second);
choose[p[0].second] = 1;
for(int i = 1; i < n; ++i){
if(p[i].first == max_v){
choose[p[i].second] = 1;
idx.pb(p[i].second);
}
else{
break;
}
}
for(int i = 0; i < idx.size(); ++i){
if(!visited[idx[i]]){
visited[idx[i]] = 1;
temp.pb(idx[i]);
dfs(idx[i]);
}
if(temp.size() > ans.size()){
ans = temp;
}
temp.clear();
}
printf("%ld\n", ans.size());
for(int i = 0; i < ans.size(); ++i){
printf("%d ", ans[i]);
}
cout << '\n';
}
int main(){
int tc;
cin >> tc;
while(tc--){
solver();
}
return 0;
}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?