제출 #669068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
669068		zaneyu	동기화 (JOI13_synchronization)	C++14	100 / 100	260 ms	27396 KiB

synchronization

/*input
5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<ll,ll>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET(v,x) lower_bound(ALL(v),x)-v.begin()
const int maxn=2e5+5;
const ll INF=0x3f3f3f3f;
const ld PI=acos(-1.0l);
const ld eps=1e-6;
const ll INF64=4e18+1;
const int MOD=1e9+7;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?"\n":"");
    return out;
}
vector<int> v[maxn];
int par[maxn][20],in[maxn],out[maxn];
int cur=1;
bool on[maxn];
int ans[maxn],pv[maxn];
void dfs(int u,int p){
    par[u][0]=p;
    in[u]=(cur++);
    for(int x:v[u]){
        if(x==p) continue;
        dfs(x,u);
    }
    out[u]=cur;
}
int bit[maxn];
void upd(int x,int v){
    while(x<maxn){
        bit[x]+=v;
        x+=lowb(x);
    }
}
int query(int x){
    int ans=0;
    while(x){
        ans+=bit[x];
        x-=lowb(x);
    }
    return ans;
}
int get(int x){
    int z=query(in[x]);
    for(int j=19;j>=0;j--){
        int b=par[x][j];
        if(b!=-1 and query(in[b])==z) x=b;
    }
    return x;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    vector<pii> ed;
    REP(i,n-1){
        int a,b;
        cin>>a>>b;
        --a,--b;
        v[a].pb(b),v[b].pb(a);
        ed.pb({a,b});
    }
    dfs(0,-1);
    REP1(j,19){
        REP(i,n){
            if(par[i][j-1]!=-1) par[i][j]=par[par[i][j-1]][j-1];
            else par[i][j]=-1;
        }
    }
    for(auto &x:ed) if(par[x.f][0]==x.s) swap(x.f,x.s);
    REP(i,n) upd(in[i],-1),upd(out[i],1),ans[i]=1;
    
    REP(i,m){
        int x;
        cin>>x;
        --x;
        int a=ed[x].f,b=ed[x].s;
        assert(par[b][0]==a);
        if(on[x]){
            ans[b]=pv[b]=ans[get(a)];
            upd(in[b],-1),upd(out[b],1);
        }   
        else{
            ans[get(a)]+=ans[b]-pv[b];
            upd(in[b],1),upd(out[b],-1);
        }
        on[x]^=1;
    }
    while(q--){
        int x;
        cin>>x;
        --x;
        cout<<ans[get(x)]<<'\n';
    }
}

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