Submission #86786

#	Time	Username	Problem	Language	Result	Execution time	Memory
86786		duy_tran	Synchronization (JOI13_synchronization)	C++14	100 / 100	545 ms	24668 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
const int maxn=(int)1e5+50;
int n,m,q,in[maxn],out[maxn],pos[maxn],cnt,on[maxn],res[maxn],last[maxn];
vector<int> a[maxn];
pii ed[maxn];
int L[4*maxn],R[4*maxn],maxx[4*maxn],leaf[maxn];

void DFS(int u)
{
    in[u]=++cnt;
    pos[cnt]=u;

    for(int v:a[u])
        if(!in[v])DFS(v);

    out[u]=cnt;
}

void START()
{
    cin>>n>>m>>q;

    for(int i=1;i<n;++i)
    {
        cin>>ed[i].first>>ed[i].second;

        a[ed[i].first].push_back(ed[i].second);
        a[ed[i].second].push_back(ed[i].first);
    }

    cnt=0;
    DFS(1);

    for(int i=1;i<=n;++i)res[i]=1;
}

void BuildTree(int id,int l,int r)
{
    L[id]=l;
    R[id]=r;

    if(l==r)
    {
        maxx[id]=out[pos[l]];
        leaf[l]=id;
        return;
    }

    int mid=(l+r)/2;

    BuildTree(id*2,l,mid);
    BuildTree(id*2+1,mid+1,r);

    maxx[id]=max(maxx[id*2],maxx[id*2+1]);
}

void Up(int id,int gt)
{
    maxx[id]=gt;
    id/=2;

    while(id>0)
    {
        maxx[id]=max(maxx[id*2],maxx[id*2+1]);
        id/=2;
    }
}

int Get(int id,int u,int p)
{
    if(L[id]>u || maxx[id]<p)return 0;

    if(L[id]==R[id])return pos[L[id]];

    int p2=Get(id*2+1,u,p);

    if(p2)return p2;

    return Get(id*2,u,p);
}

void NEXT()
{
    BuildTree(1,1,n);

    for(int i=1;i<=m;++i)
    {
        int id;
        cin>>id;

        int u=ed[id].first;
        int v=ed[id].second;

        if(in[u]>in[v])swap(u,v);

        int root=Get(1,in[u],out[u]);

        //cout<<u<<" "<<v<<" "<<root<<'\n';

        if(!on[id])
        {
            on[id]=1;

            res[root]+=res[v]-last[v];
            Up(leaf[in[v]],0);
        }

        else
        {
            on[id]=0;

            res[v]=last[v]=res[root];

            Up(leaf[in[v]],out[v]);
        }
    }

    for(int i=1;i<=q;++i)
    {
        int u;
        cin>>u;

        int root=Get(1,in[u],out[u]);

        cout<<res[root]<<'\n';
    }
}

int main()
{
    START();
    NEXT();
}

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