fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. // template {{{
  8. #define pb push_back
  9. #define eb emplace_back
  10. #define mp make_pair
  11. #define mt make_tuple
  12. #define lb lower_bound
  13. #define ub upper_bound
  14. #define resz resize
  15. #define deb(x) cout<<#x<<" "<<x<<endl
  16. #define f first
  17. #define s second
  18. #define u_s unordered_set
  19. #define u_m unordered_map
  20. #define p_q priority_queue
  21.  
  22. #define sz(x) int((x).size())
  23. #define all(x) (x).begin(), (x).end()
  24.  
  25. #define FOR(i, a, b) for (int i = (a); i < (b); i++)
  26. #define F0R(i, a) for (int i = 0; i < (a); i++)
  27. #define FORd(i, a, b) for (int i = (b)-1; i >= (a); i--)
  28. #define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
  29. #define trav(a, x) for (auto& a : x)
  30.  
  31. #define sort_by(x, y) sort(all(x), [&](const auto& a, const auto& b) { return y; })
  32.  
  33. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  34.  
  35. using ll = long long;
  36. using vi = vector<int>;
  37. using vvi = vector<vi>;
  38. using vll = vector<ll>;
  39. using vvll = vector<vll>;
  40. using vb = vector<bool>;
  41. using vd = vector<double>;
  42. using vs = vector<string>;
  43.  
  44. using pii = pair<int, int>;
  45. using pll = pair<ll, ll>;
  46. using pdd = pair<double, double>;
  47.  
  48. using vpii = vector<pii>;
  49. using vpll = vector<pll>;
  50. using vpdd = vector<pdd>;
  51.  
  52. template<typename T> void ckmin(T& a, const T& b) { a = min(a, b); }
  53. template<typename T> void ckmax(T& a, const T& b) { a = max(a, b); }
  54.  
  55. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  56.  
  57. namespace __input {
  58.     template<class T1, class T2> void re(pair<T1,T2>& p);
  59.     template<class T> void re(vector<T>& a);
  60.     template<class T, size_t SZ> void re(array<T,SZ>& a);
  61.  
  62.     template<class T> void re(T& x) { cin >> x; }
  63.     void re(double& x) { string t; re(t); x = stod(t); }
  64.     template<class Arg, class... Args> void re(Arg& first, Args&... rest) {
  65.         re(first); re(rest...);
  66.     }
  67.  
  68.     template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
  69.     template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
  70.     template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
  71. }
  72. using namespace __input;
  73.  
  74. namespace __output {
  75.     template<class T1, class T2> void pr(const pair<T1,T2>& x);
  76.     template<class T, size_t SZ> void pr(const array<T,SZ>& x);
  77.     template<class T> void pr(const vector<T>& x);
  78.     template<class T> void pr(const set<T>& x);
  79.     template<class T1, class T2> void pr(const map<T1,T2>& x);
  80.  
  81.     template<class T> void pr(const T& x) { cout << x; }
  82.     template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
  83.         pr(first); pr(rest...);
  84.     }
  85.  
  86.     template<class T1, class T2> void pr(const pair<T1,T2>& x) {
  87.         pr("{",x.f,", ",x.s,"}");
  88.     }
  89.     template<class T, bool pretty = true> void prContain(const T& x) {
  90.         if (pretty) pr("{");
  91.         bool fst = 1; for (const auto& a: x) pr(!fst?pretty?", ":" ":"",a), fst = 0;
  92.         if (pretty) pr("}");
  93.     }
  94.     template<class T> void pc(const T& x) { prContain<T, false>(x); pr("\n"); }
  95.     template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
  96.     template<class T> void pr(const vector<T>& x) { prContain(x); }
  97.     template<class T> void pr(const set<T>& x) { prContain(x); }
  98.     template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
  99.  
  100.     void ps() { pr("\n"); }
  101.     template<class Arg> void ps(const Arg& first) {
  102.         pr(first); ps();
  103.     }
  104.     template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
  105.         pr(first," "); ps(rest...);
  106.     }
  107. }
  108. using namespace __output;
  109.  
  110. #define TRACE(x) x
  111. #define __pn(x) pr(#x, " = ")
  112. #define pd(...) __pn((__VA_ARGS__)), ps(__VA_ARGS__), cout << flush
  113.  
  114. namespace __algorithm {
  115.     template<typename T> void dedup(vector<T>& v) {
  116.         sort(all(v)); v.erase(unique(all(v)), v.end());
  117.     }
  118.     template<typename T> typename vector<T>::const_iterator find(const vector<T>& v, const T& x) {
  119.         auto it = lower_bound(all(v), x); return it != v.end() && *it == x ? it : v.end();
  120.     }
  121.     template<typename T> size_t index(const vector<T>& v, const T& x) {
  122.         auto it = find(v, x); assert(it != v.end() && *it == x); return it - v.begin();
  123.     }
  124.  
  125.     template<typename T1, typename T2> typename vector<pair<T1, T2>>::iterator lower_bound(
  126.             const vector<pair<T1, T2>>& v, const T1& x) {
  127.         return lower_bound(all(v), x, [](pair<T1, T2> a, pair<T1, T2> b) { return a.f < b.f; });
  128.     }
  129.     template<typename T1, typename T2> typename vector<pair<T1, T2>>::iterator upper_bound(
  130.             const vector<pair<T1, T2>>& v, const T1& x) {
  131.         return upper_bound(all(v), x, [](pair<T1, T2> a, pair<T1, T2> b) { return a.f < b.f; });
  132.     }
  133.     template<typename T> T POW(T b, T p){
  134.         T Ans = 1;
  135.         while(p){if(p&1) Ans=(Ans*b); b*=b, p>>=1;} return Ans;}
  136. }
  137. using namespace __algorithm;
  138.  
  139. struct __monostate {
  140.     friend istream& operator>>(istream& is, const __attribute__((unused))__monostate& ms) { return is; }
  141.     friend ostream& operator<<(ostream& os, const __attribute__((unused))__monostate& ms) { return os; }
  142. } ms;
  143.  
  144. namespace __io {
  145.     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
  146.     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
  147.     void setIO(string s = "") {
  148.         ios_base::sync_with_stdio(0); cin.tie(0);
  149.         cout << setprecision(15);
  150.         if (sz(s)) { setIn(s+".in"), setOut(s+".out"); }
  151.     }
  152. }
  153. using namespace __io;
  154. // }}}
  155. // AUTHOR:DaddyCool__69
  156. const int N = 2e5+1;
  157. int t, n, m, k, a1, b1;
  158. vi sol, ans;
  159. bool visited[N], rt[N];
  160. vi g[N];
  161. void dfs(int u)
  162. {
  163.     sol.pb(u);
  164.     visited[u] = 1;
  165.     for(auto v:g[u])
  166.     {
  167.         if(visited[v] || !rt[v])
  168.             continue;
  169.         dfs(v);
  170.     }
  171. }
  172. int main()
  173. {
  174.     ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  175.     re(t);
  176.     while(t--)
  177.     {
  178.         ans.clear();
  179.         sol.clear();
  180.         re(n, m);
  181.         vi a(n+1), b(n+1);
  182.         FOR(i, 1, n+1)
  183.             re(a[i]);
  184.         FOR(i, 1, n+1)
  185.         {
  186.             g[i].clear();
  187.             re(b[i]);
  188.             visited[i] = 0;
  189.             rt[i] = 0;
  190.             //cout<<rt[i]<<" ";
  191.         }
  192.         a1 = a[1];
  193.         b1 = b[1];
  194.         FOR(i, 2, n+1)
  195.             if(a[i]*b1>b[i]*a1)
  196.                 a1 = a[i], b1 = b[i];
  197.         FOR(i, 0, m)
  198.         {
  199.             int u, v;
  200.             re(u, v);
  201.             g[u].pb(v);
  202.             g[v].pb(u);
  203.         }
  204.         FOR(i, 1, n+1)
  205.         {
  206.             if(a[i]*b1==b[i]*a1)
  207.                 rt[i] = 1;
  208.             else
  209.                 rt[i] = 0;
  210.         }
  211.         for(int i = n; i>=1; i--)
  212.         {
  213.             if(!visited[i] && rt[i])
  214.             {
  215.                 sol.clear();
  216.                 dfs(i);
  217.                 if(sz(sol)>sz(ans))
  218.                     ans = sol;
  219.             }
  220.         }
  221.         ps(sz(ans));
  222.         for(int x:ans)
  223.             cout<<x<<" ";
  224.         cout<<endl;
  225.     }
  226. }
  227.  
Success #stdin #stdout 0s 8252KB
comments (?)
stdin
copy 
1
3 3
10 1 2
5 1 1 
1 2
2 3
1 3
stdout
copy 
2
3 1
https://ideone.com/EEDtu4
language:
C++14 (gcc 8.3)
created:
5 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!