fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC target ("avx2")
  4. #pragma GCC optimization ("O3")
  5. #pragma GCC optimization ("unroll-loops")
  6. #define all(x) x.begin(),x.end()
  7. #define ll long long int
  8. const int MAX = 1e6+7;
  9. const int MOD = 998244353;
  10.  
  11. int cnt = 0,maxi = 0;
  12. vector<double> val;
  13. vector<int> res,anss,vis;
  14.  
  15. void dfs(int u,double mx,vector<int> adj[])
  16. {
  17.     vis[u] = 1;
  18.     cnt++;
  19.     anss.push_back(u);
  20.  
  21.     for(int i = 0;i<adj[u].size();i++)
  22.     {
  23.         int v = adj[u][i];
  24.         if(!vis[v] && val[v] == mx) dfs(v,mx,adj);
  25.     }
  26. }
  27.  
  28. int main(int argc, char const *argv[])
  29. {
  30.     int t; cin>>t;
  31.     while(t-->0)
  32.     {
  33.       cnt = maxi = 0;
  34.  
  35.       int n,m; cin>>n>>m;
  36.       double mx = 0;
  37.       vector<int> a(n),b(n),adj[n+1];
  38.       val.clear();
  39.       anss.clear();
  40.       res.clear();
  41.       val.resize(n+1);
  42.       vis.resize(n+1,0);
  43.  
  44.       for(int i = 0;i<n;i++) cin>>a[i];
  45.       for(int i = 0;i<n;i++) cin>>b[i];
  46.       for(int i = 0;i<n;i++) val[i+1] = a[i]/b[i],mx = max(mx,val[i+1]);
  47.  
  48.       for(int i = 0;i<m;i++){
  49.         int u,v;
  50.         cin>>u>>v;
  51.         adj[u].push_back(v);
  52.         adj[v].push_back(u);
  53.       }
  54.  
  55.       for(int i=1;i<=n;i++)
  56.         if(val[i] == mx)
  57.         {
  58.           anss.clear();
  59.           cnt = 0;
  60.           dfs(i,mx,adj);
  61.           if(cnt>maxi) res = anss,maxi = cnt;
  62.         }
  63.  
  64.       cout<<res.size()<<'\n';
  65.       for(int i = 0;i<res.size();i++) cout<<res[i]<<" ";
  66.       cout<<'\n';
  67.     }
  68.  
  69.   return 0;
  70. }
  71.  
Runtime error #stdin #stdout 0s 5516KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/sBtBJU
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!