Submission #882197

#	Time	Username	Problem	Language	Result	Execution time	Memory
882197		abcvuitunggio	Synchronization (JOI13_synchronization)	C++17	100 / 100	276 ms	36372 KiB

synchronization

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q,x[100001],y[100001],d,c,last[100001],s[100001],res[100001],tin[100001],tout[100001],t,p[100001][20],ft[100001][2];
vector <int> ke[100001];
void update(int i, int j, int val){
    for (;i<=n;i+=i&(-i))
        ft[i][j]+=val;
}
int get(int i, int j){
    int res=0;
    for (;i;i-=i&(-i))
        res+=ft[i][j];
    return res;
}
int get(int u){
    return get(tout[u],1)-get(tin[u]-1,1);
}
void dfs(int u, int par){
    tin[u]=++t;
    for (int v:ke[u])
        if (v!=par){
            p[v][0]=u;
            for (int i=1;i<20;i++)
                p[v][i]=p[p[v][i-1]][i-1];
            dfs(v,u);
        }
    tout[u]=t;
}
int f(int u){
    for (int i=19;i>=0;i--)
        if (p[u][i]&&get(tin[u],0)-get(tin[p[u][i]],0)==(1<<i))
            u=p[u][i];
    return u;
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> m >> q;
    for (int i=1;i<n;i++){
        cin >> x[i] >> y[i];
        ke[x[i]].push_back(y[i]);
        ke[y[i]].push_back(x[i]);
    }
    fill(res,res+n+1,1);
    dfs(1,1);
    for (int i=1;i<=n;i++){
        update(tin[i],1,1);
        if (i>1)
            update(tin[p[i][0]],1,-1);
    }
    for (int i=1;i<n;i++)
        if (x[i]==p[y[i]][0])
            swap(x[i],y[i]);
    while (m--){
        cin >> d;
        s[d]^=1;
        update(tin[x[d]],0,s[d]*2-1);
        update(tout[x[d]]+1,0,1-s[d]*2);
        int u=f(y[d]);
        if (s[d]){
            int val=get(x[d])-last[d];
            update(tin[y[d]],1,val);
            if (u!=1)
                update(tin[p[u][0]],1,-val);
            res[u]+=val;
            continue;
        }
        last[d]=get(x[d]);
        res[x[d]]=res[u];
    }
    while (q--){
        cin >> c;
        cout << res[f(c)] << '\n';
    }
}

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