fork download
copy 
  1.     #include <bits/stdc++.h>
  2.     #define ll long long
  3.     using namespace std;
  4.  
  5.     const ll INF = (ll)-4e18;
  6. struct DSU{   
  7.     vector<int>parent,gsize,minimal,maximal,score;
  8.     int comps;
  9.     int mxcmp;
  10.     DSU(int maxi){
  11.         score=parent=gsize=minimal=maximal=vector<int>(maxi+5);
  12.         comps=maxi;
  13.         mxcmp=1;
  14.         for(int i=0;i<=maxi;i++){
  15.            minimal[i]=maximal[i]=parent[i]=i,gsize[i]=1,score[i]=0;
  16.         }
  17.         }
  18.         int find_leader(int node){
  19.             return parent[node]=(parent[node]==node?node:find_leader(parent[node]));
  20.         }
  21.         bool samel(int node1,int node2){
  22.             return find_leader(node1)==find_leader(node2);
  23.         }
  24.         void union_set(int node1,int node2){
  25.             int u=find_leader(node1),v=find_leader(node2);
  26.             if(u==v)return;
  27.             if(gsize[u]<gsize[v]&&find_leader(u)!=0)swap(u,v);
  28.             gsize[u]+=gsize[v],parent[v]=u;
  29.             score[v]-=score[u];
  30.             comps--;
  31.             mxcmp=max(gsize[u],mxcmp);
  32.             maximal[u]=max(maximal[u],maximal[v]);
  33.            minimal[u]=min(minimal[u],minimal[v]);
  34.         }
  35.         int find_min(int u){
  36.             int v=find_leader(u);
  37.             return minimal[v];
  38.         }
  39.         int find_max(int u){
  40.             int v=find_leader(u);
  41.             return maximal[v];
  42.         }
  43.         int largest_comp(){
  44.             return mxcmp;
  45.         }
  46.         void score_update(int u,int x){
  47.            int v=find_leader(u);
  48.            score[v]+=x;
  49.         }
  50.         int get_score(int u){
  51.             int v=find_leader(u);
  52.             int ans=(v==u?score[v]:score[v]+score[u]);
  53.             return ans;
  54.         }
  55.     };
  56.     struct Edge{
  57.         int u,v;
  58.         long long w;
  59.  
  60.         Edge(int _u=0,int _v=0,long long _w = 0):u(_u),v(_v),w(_w){}
  61.  
  62.         friend istream& operator>>(istream &in, Edge &e){
  63.             in>>e.u>>e.v>>e.w;
  64.             return in;
  65.         }
  66.  
  67.         void inv(){
  68.             w *= -1;
  69.         }
  70.     };
  71.     bool cs(const Edge& fs,const Edge& sec){
  72.         return fs.w<sec.w;
  73.     }
  74.     vector<Edge>edges;
  75.     vector<vector<long long>>adj;
  76.     vector<bool>visited;
  77.     vector<ll>dists;
  78.     vector<vector<long long>>costs;
  79.     void dfs(ll n){
  80.         visited[n]=1;
  81.        for(ll&a:adj[n]){
  82.         if(!visited[a]){
  83.             visited[a]=1;
  84.             dists[a]=dists[n]+costs[n][a];
  85.             dfs(a);
  86.         }
  87.        }
  88.     }
  89.   int main(){
  90.     ios_base::sync_with_stdio(false);
  91.     cin.tie(NULL);
  92.     int n,m;
  93.     cin>>n>>m;
  94.     DSU dsu(n);
  95.     vector<pair<int,int>>init(n);
  96.     map<pair<int,int>,int>mp;
  97.      vector<bool>survived(2*n,1);
  98.      vector<int>rights(n);
  99.      vector<int>lefts(n);
  100.      vector<pair<int,int>>valids(n*2);
  101.     vector<pair<int,int>>cuts(m);
  102.     for(int i=0;i<n;i++){
  103.         int x,y;
  104.         cin>>x>>y;
  105.         x--,y--;
  106.         init[i]={x,y};
  107.         if(x<0)survived[i*2]=0;
  108.         else mp[{i,x}]=i*2;
  109.         valids[i*2]={i,x};
  110.         if(y<0)survived[i*2+1]=0;
  111.         else mp[{i,y}]=i*2+1;
  112.         valids[i*2+1]={i,y};
  113.         lefts[i]=x;
  114.         rights[i]=y;
  115.     }
  116.     for(int i=0;i<m;i++){
  117.         int x,y;
  118.         cin>>x>>y;
  119.         x--;
  120.         if(y==1){
  121.          auto it=mp.find({x,lefts[x]});
  122.             if(it!=mp.end()){
  123.                 survived[mp[{x,lefts[x]}]]=0;
  124.             }
  125.             cuts[i]={x,lefts[x]};
  126.         }
  127.         else{
  128.             auto it=mp.find({x,rights[x]});
  129.             if(it!=mp.end()){
  130.                 survived[mp[{x,rights[x]}]]=0;
  131.             }
  132.             cuts[i]={x,rights[x]};
  133.         }
  134.     }
  135.     for(int i=0;i<2*n;i++){
  136.         if(survived[i]){
  137.             dsu.union_set(valids[i].first,valids[i].second);
  138.         }
  139.     }
  140.     int cnt=1;
  141.     vector<int> secs(n,-1);
  142. reverse(cuts.begin(),cuts.end());
  143.  
  144. for(int i=0;i<m;i++){
  145.     dsu.union_set(cuts[i].first,cuts[i].second);
  146.  
  147.     for(int j=0;j<n;j++){
  148.         if(dsu.find_leader(j)==dsu.find_leader(0)&&secs[j]==-1&&j!=0){
  149.             secs[j]=m-i-1;
  150.         }
  151.     }
  152. }
  153.     for(int i=0;i<n;i++){
  154.  
  155.      cout<<secs[i]<<"\n";
  156.     }
  157.     return 0;
  158.   }
  159.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HkwKiJ
language:
C++14 (gcc 8.3)
created:
3 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!