Submission #1288660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288660		wowwowwow	Synchronization (JOI13_synchronization)	C++20	100 / 100	179 ms	24112 KiB

synchronization

#include <bits/stdc++.h>
#define ll long long
#define all(v) v.begin(),v.end()
#define MASK(i) (1LL << (i))
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define forr(i,l,r,add) for(int i = l;i <= r; i = i + add)
#define fodd(i,l,r,sub) for(int i = l;i >= r ; i = i - sub)
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
#define rand rd

long long Rand(long long l , long long h){
    assert(l <= h);
    return l + 1ll * rd() % (h - l + 1) * (rd() % (h - l + 1)) % (h - l + 1);
}

//////////////////////////////////////////////////////////// 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].push_back(v);
        adj[v].push_back(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(false);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}

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