Submission #757449

#	Time	Username	Problem	Language	Result	Execution time	Memory
757449		bgnbvnbv	Synchronization (JOI13_synchronization)	C++14	100 / 100	516 ms	40992 KiB

synchronization

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
// y tuong bai nay la luu root tai node cao nhat trong tplt
ll in[maxN],out[maxN],P[maxN][19];
int tg=0;
vector<pli>g[maxN];
ll h[maxN],pos[maxN];
void dfs(ll u,ll p)
{
    in[u]=++tg;
    P[u][0]=p;
    for(int i=1;i<=18;i++) P[u][i]=P[P[u][i-1]][i-1];
    for(auto zz:g[u])
    {
        if(zz.fi!=p)
        {
            h[zz.fi]=h[u]+1;
            pos[zz.se]=zz.fi;
            dfs(zz.fi,u);
        }
    }
    out[u]=tg;
}
ll n,bit[maxN];
void upd(ll u,ll val)
{
    ll i=in[u];
    while(i<=n)
    {
        bit[i]+=val;
        i+=(i&(-i));
    }
    i=out[u]+1;
    while(i<=n)
    {
        bit[i]-=val;
        i+=i&(-i);
    }
}
ll get(ll u)
{
    ll i=in[u];
    ll ans=0;
    while(i>0)
    {
        ans+=bit[i];
        i-=i&(-i);
    }
    return ans;
}
ll findp(ll u)
{
    ll v=u;
    for(int i=18;i>=0;i--)
    {
        ll x=P[u][i];
        if(get(v)-get(x)==h[v]-h[x]) u=x;
    }
    return u;
}
ll m,q,c[maxN];
ll a[maxN],b[maxN];
void solve()
{
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++) a[i]=1,c[i]=0;
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb({v,i});
        g[v].pb({u,i});
    }
    dfs(1,1);
    for(int i=1;i<=m;i++)
    {
        ll id;
        cin >> id;
        upd(pos[id],(c[id]^1)-c[id]);
        if(c[id]==0)
        {
            ll v=pos[id];
            //ll u=P[v][0];
            ll u=findp(v);
            a[u]=a[u]+a[v]-b[v];
            a[v]=0;
        }
        else
        {
            ll v=pos[id];
            a[v]=a[findp(P[v][0])];
            b[v]=a[findp(P[v][0])];
        }
        c[id]^=1;
    }
    //cout << get(4)-get(2)<<' '<<h[4]-h[2]<<'\n';
    for(int i=1;i<=q;i++)
    {
        ll x;
        cin >> x;
        cout << a[findp(x)]<<'\n';
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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