Submission #1136531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136531		Psiuk_Yurii	동기화 (JOI13_synchronization)	C++20	0 / 100	130 ms	42068 KiB

synchronization

/*In FISH at EGOI25 I trust*/
/*In FISH at EGOI25 I trust*/
/*In FISH at EGOI25 I trust*/
/*In FISH at EGOI25 I trust*/
/*In FISH at EGOI25 I trust*/
#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppl;

struct edge{
   ll u,w;
};
edge p[200009];
ll n,q,m,v1,v2,eu[200009],e,a[200009],b[200009],dv[200009][25],h,c[200009],T[400009],sz[400009],g;
vector<ll> A[200009];
void add(int pos,int val){
   pos++;
   for(int i=pos;i<400000;i+=-i&i) T[i]+=val;
}
ll pref(int pos){
   ll S=0;
   pos++;
   for(int i=pos;i>0;i-=-i&i) S+=T[i];
   return S;
}
void ff(int v,int k){
   add(eu[v],k);
   add(eu[v]+sz[v],-k);
}
void dfs(int v,int par){
  a[v]=1;
  e++;
  eu[v]=e;
  //cout<<"eu "<<v<<" "<<e<<endl;
  dv[v][0]=par;
  sz[v]=1;
  for(int i=1;i<=h;i++) dv[v][h]=dv[dv[v-1][h-1]][h-1];
  for(auto to:A[v]) if(to!=par) {dfs(to,v); sz[v]+=sz[to];}
  ff(v,1);
}
ll boss(int v){
    //cout<<"B "<<v;
   ll U=pref(eu[v]);
   for(int i=h;i>=0;i--){
      if(pref(eu[dv[v][i]])==U) v=dv[v][i];
   }
   //cout<<" "<<v<<endl;
   return v;
}
void print(){
    cout<<"/pf"<<endl;;
for(int i=1;i<=n;i++) cout<<i<<" "<<pref(i)<<endl;
cout<<"/pe"<<endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    h=22;
    cin>>n>>q>>m;
    for(int i=1;i<n;i++){
        cin>>v1>>v2;
        A[v1].push_back(v2);
        A[v2].push_back(v1);
        p[i]={v1,v2};
    }
    dfs(1,1);
    for(int i=1;i<n;i++) if(eu[p[i].u]>eu[p[i].w]) swap(p[i].u,p[i].w);
   // print();

    for(int i=1;i<=q;i++){
        cin>>g;
        v1=p[g].u; v2=p[g].w;
        if(c[v2]){
            c[v2]=0;
            a[v2]=b[v2]=a[boss(v1)];
            //cout<<"- "<<v2<<" "<<a[v2]<<endl;
            ff(v2,1);
        }
        else{
            c[v2]=1;
            a[boss(v1)]+=a[v2]-b[v2];
           // cout<<"B "<<v1<<" "<<boss(v1)<<endl;
            //cout<<"+ "<<boss(v1)<<" "<<a[boss(v1)]<<endl;
            ff(v2,-1);
        }
        //print();

    }
    for(int i=1;i<=m;i++){
        cin>>g;
       // cout<<"a "<<a[boss(g)]<<"\n";
        cout<<a[boss(g)]<<"\n";
    }



    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40