fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //variable
  4. #define ld long double
  5. #define ll long long
  6. #define db double
  7. #define ii pair<int,int>
  8. #define f first
  9. #define s second
  10. #define mp make_pair
  11. #define mt make_tuple
  12. //vector
  13. #define pb push_back
  14. #define all(v) v.begin(),v.end()
  15. #define len(a) (int)a.length()
  16. #define sz(a) (int)a.size()
  17. //mask
  18. #define BIT(i) (1LL<<(i))
  19. //better code, debugger
  20. #define watch(n) cerr << #n << ": " << n << endl
  21. #define debug(x) for (auto p: x) cerr<<p<<' ';cerr<<endl
  22. #define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
  23. #define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
  24. #define fIlE "closing."
  25. //auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  26. //mt19937 RAND(seed);
  27. const int mod = 998244353;
  28. inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;}
  29. inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;}
  30. inline int mul(int u,int v){return (ll)u*v%mod;}
  31. int n, m;
  32. const int N = 3000 + 2;
  33. ii edge[N];
  34. vector<int> a[N], ok[N];
  35. int per[N];
  36. bool del[N];
  37. struct DSU{
  38.     int root = 0;
  39. };
  40. DSU dsu[N];
  41.  
  42. int findset(int u)
  43. {
  44.     return dsu[u].root == u ? u : dsu[u].root = findset(dsu[u].root);
  45. }
  46. void solve()
  47. {
  48.     cin >> n >> m;
  49.     forw(i, 1, m){
  50.         int u, v;
  51.         cin >> u >> v;
  52.         edge[i] = mp(u, v);
  53.         a[u].pb(i);
  54.         a[v].pb(i);
  55.     }
  56.     forw(i, 1, n){
  57.         cin >> per[i];
  58.         for (int e : a[per[i]])
  59.         {
  60.             if (!del[e])
  61.             {
  62.                 del[e] = 1;
  63.                 ok[i].pb(e);
  64.             }
  65.         }
  66.     }
  67.     vector<string> ans;
  68.     int cnt = 0;
  69.     ford(i, n, 1){
  70.         dsu[per[i]].root = per[i];
  71.         ++cnt;
  72.         for (int e : ok[i])
  73.         {
  74.             int u = edge[e].f, v = edge[e].s;
  75.             u = findset(u), v = findset(v);
  76.             if (u == v) continue;
  77.             dsu[u].root = v;
  78.             cnt--;
  79.         }
  80.         ans.pb(cnt <= 1 ? "YES\n" : "NO\n");
  81.     }
  82.     ford(i, n - 1, 0) cout << ans[i];
  83. }
  84. signed main()
  85. {
  86.     ios_base::sync_with_stdio(false);
  87.     cin.tie(0);
  88.     if (fopen(fIlE"in", "r"))
  89.         freopen(fIlE"in","r",stdin), freopen(fIlE"out","w",stdout);
  90.     //time_t TIME_TU=clock();
  91.     int t=1;
  92. //    cin>>t;
  93.     while(t--)
  94.         solve();
  95.     //time_t TIME_TV=clock();
  96.     //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cVH3MO
language:
C++ (gcc 8.3)
created:
4 days 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!