Submission #1177482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177482		vnedu	Synchronization (JOI13_synchronization)	C++20	100 / 100	177 ms	24132 KiB

synchronization

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

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e5 + 15;
int numNode,numState,numQuery,dep[N],st[N],en[N],tg=0,bit[N*2],up[N][20];
vector<int> adj[N];
ii edge[N];
void add(int x, int val)
{
    while (x<=2*numNode)
    {
        bit[x]+=val;
        x+=x&-x;
    }
}
int get(int x)
{
    int ans=0;
    while (x>=1)
    {
        ans+=bit[x];
        x-=x&-x;
    }
    return ans;
}
void dfs(int u, int pa)
{
    up[u][0]=pa;
    for (int j=1; j<20; ++j) if ((1<<j)<dep[u]) up[u][j]=up[up[u][j-1]][j-1];
    st[u]=++tg;
    for (int v : adj[u]) if (v!=pa)
    {
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
    en[u]=++tg;
}
int findRoot(int u)
{
    for (int j=19; j>=0; --j) if ((1<<j)<dep[u])
    {
        int v=up[u][j];
        if (dep[u]-dep[v]==get(st[u])-get(st[v])) u=v;
    }
    return u;
}
int lst[N],uni[N];
void solve()
{
    cin>>numNode>>numState>>numQuery;
    for (int i=1; i<numNode; ++i)
    {
        int u,v; cin>>u>>v;
        edge[i]={u,v};
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dep[1]=1;
    dfs(1,-1);
    for (int i=1; i<numNode; ++i)
    {
        if (dep[edge[i].fi]<dep[edge[i].se]) swap(edge[i].fi,edge[i].se);
    }
    for (int i=1; i<=numNode; ++i) uni[i]=1;
    for (int tri=1; tri<=numState; ++tri)
    {
        int x; cin>>x;
        if (lst[x]==-1)
        {
            int u=edge[x].fi,v=edge[x].se;
            uni[u]=uni[findRoot(v)];
            add(st[u],-1);
            add(en[u]+1,1);
            lst[x]=uni[u];
        }
        else
        {
            int u=edge[x].fi,v=edge[x].se;
            int &cur=uni[findRoot(v)];
            cur+=uni[u];
            cur-=lst[x];
            add(st[u],1);
            add(en[u]+1,-1);
            lst[x]=-1;
        }
    }
    while (numQuery--)
    {
        int x; cin>>x;
        cout<<uni[findRoot(x)]<<'\n';
    }
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

//    #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
//    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

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