Submission #1186985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186985		maxFedorchuk	Synchronization (JOI13_synchronization)	C++20	100 / 100	524 ms	28672 KiB

synchronization

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

const long long MX=2e5+10;
const long long lg=30;
vector < int > mas[MX];

pair < int , int > rb[MX];

int tin[MX],tou[MX],timer=0;
int lca[lg][MX];

int cur[MX],prv[MX],u[MX];

int ms[MX];
int n,m,q;

void DFS(int zar,int mun)
{
    timer++;
    tin[zar]=timer;

    lca[0][zar]=mun;
    for(int i=1;i<lg;i++)
    {
        lca[i][zar]=lca[i-1][lca[i-1][zar]];
    }

    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            DFS(u,zar);
        }
    }

    tou[zar]=timer;
}

int fget(int in)
{
    int rt=0;
    while(in>=0)
    {
        rt+=ms[in];
        in=(in&(in+1))-1;
    }

    return rt;
}

void upd(int in,int zn)
{
    while(in<=n)
    {
        ms[in]+=zn;
        in|=(in+1);
    }
}

int fgetlca(int a)
{
    for(int i=lg-1;i>=0;i--)
    {
        if(fget(tin[lca[i][a]])==fget(tin[a]))
        {
            a=lca[i][a];
        }
    }

    return a;
}
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>m>>q;

    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;

        mas[a].push_back(b);
        mas[b].push_back(a);

        rb[i]=make_pair(a,b);
    }

    DFS(1,0);
    tou[0]=timer;

    for(int i=0;i<=n;i++)
    {
        upd(tin[i],1);
        upd(tou[i]+1,-1);

        cur[i]=1;
        prv[i]=0;
    }

    while(m--)
    {
        int in;
        cin>>in;

        int a=rb[in].first,b=rb[in].second;

        if(lca[0][a]==b)
        {
            swap(a,b);
        }

        if(!u[in])
        {
            cur[fgetlca(a)]+=(cur[b]-prv[b]);

            upd(tin[b],-1);
            upd(tou[b]+1,1);
        }
        else
        {
            cur[b]=prv[b]=cur[fgetlca(a)];
            upd(tin[b],1);
            upd(tou[b]+1,-1);
        }

        u[in]^=1;
    }

    while(q--)
    {
        int in;
        cin>>in;

        cout<<cur[fgetlca(in)]<<"\n";
    }

    return 0;
}

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