oj.uz

Submission #86786

# Submission time Handle Problem Language Result Execution time Memory
86786 2018-11-27T12:38:52 Z duy_tran Synchronization (JOI13_synchronization) C++14
100 / 100
 545 ms 24668 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2856 KB Output is correct
4 Correct 4 ms 2932 KB Output is correct
5 Correct 4 ms 2980 KB Output is correct
6 Correct 6 ms 3060 KB Output is correct
7 Correct 28 ms 4228 KB Output is correct
8 Correct 27 ms 4436 KB Output is correct
9 Correct 26 ms 4684 KB Output is correct
10 Correct 324 ms 15748 KB Output is correct
11 Correct 268 ms 18016 KB Output is correct
12 Correct 256 ms 23356 KB Output is correct
13 Correct 260 ms 23356 KB Output is correct
14 Correct 205 ms 23356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 23356 KB Output is correct
2 Correct 190 ms 23356 KB Output is correct
3 Correct 168 ms 24008 KB Output is correct
4 Correct 187 ms 24008 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24008 KB Output is correct
2 Correct 4 ms 24008 KB Output is correct
3 Correct 5 ms 24008 KB Output is correct
4 Correct 4 ms 24008 KB Output is correct
5 Correct 5 ms 24008 KB Output is correct
6 Correct 7 ms 24008 KB Output is correct
7 Correct 45 ms 24008 KB Output is correct
8 Correct 545 ms 24584 KB Output is correct
9 Correct 520 ms 24584 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 24584 KB Output is correct
2 Correct 381 ms 24584 KB Output is correct
3 Correct 425 ms 24668 KB Output is correct
4 Correct 371 ms 24668 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24668 KB Output is correct
2 Correct 4 ms 24668 KB Output is correct
3 Correct 4 ms 24668 KB Output is correct
4 Correct 4 ms 24668 KB Output is correct
5 Correct 10 ms 24668 KB Output is correct
6 Correct 47 ms 24668 KB Output is correct
7 Correct 534 ms 24668 KB Output is correct
8 Correct 508 ms 24668 KB Output is correct
9 Correct 450 ms 24668 KB Output is correct
10 Correct 433 ms 24668 KB Output is correct
11 Correct 430 ms 24668 KB Output is correct
12 Correct 389 ms 24668 KB Output is correct
13 Correct 364 ms 24668 KB Output is correct