fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,start,end,jump) for(int i=(start),_end=(end);i<=_end;i+=(jump))
  3. #define fi first
  4. #define se second
  5. #define ps(any) push_back(any)
  6. using namespace std;
  7.  
  8. const int maxn=2e5+3;
  9. const int maxm=4e5+3;
  10.  
  11. int n, res[maxn],m;
  12. pair<int,int> hands[maxn];
  13. pair<int,int> event[maxm];
  14. vector<vector<int>> a;
  15. vector<bool> visited;
  16.  
  17. void READ(){
  18.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  19.     cin>>n>>m;
  20.     a.resize(n+1);
  21.     FOR(i,1,n,1){
  22.         cin>>hands[i].fi>>hands[i].se;
  23.         if(hands[i].fi!=-1){
  24.             a[i].ps(hands[i].fi);
  25.             a[hands[i].fi].ps(i);
  26.         }
  27.         if(hands[i].se!=-1){
  28.             a[i].ps(hands[i].se);
  29.             a[hands[i].se].ps(i);
  30.         }
  31.     }
  32.     FOR(i,1,n,1) sort(a[i].begin(),a[i].end());
  33.     FOR(i,1,m,1) cin>>event[i].fi>>event[i].se;
  34. }
  35.  
  36. void REMOVE(int u, int v)
  37. {
  38.     auto x = lower_bound(a[u].begin(),a[u].end(),v);
  39.     a[u].erase(x);
  40.     x = lower_bound(a[v].begin(), a[v].end(), u);
  41.     a[v].erase(x);
  42. }
  43.  
  44. void bfs(int v)
  45. {
  46.     visited[v]=true;
  47.     for(int i=0;i<a[v].size();i++){
  48.         if(!visited[a[v][i]])
  49.             bfs(a[v][i]);
  50.     }
  51. }
  52.  
  53. void DO(){
  54.     fill(res+1,res+n+1,-1);
  55.     FOR(i,1,m,1)
  56.     {
  57.         visited.assign(n+1,false);
  58.         if(event[i].se==1)
  59.             REMOVE(event[i].fi,hands[event[i].fi].fi);
  60.         else REMOVE(event[i].fi,hands[event[i].fi].se);
  61.         bfs(1);
  62.         FOR(j,1,n,1) if(!visited[j]) if(res[j]==-1) res[j]=i-1;
  63.     }
  64.     FOR(i,1,n,1) cout<<res[i]<<'\n';
  65. }
  66.  
  67. int main()
  68. {
  69.     READ();
  70.     DO();
  71. }
  72.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0SiJo7
language:
C++14 (gcc 8.3)
created:
280 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!