제출 #1244948

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244948		nguyenhuythach	동기화 (JOI13_synchronization)	C++20	100 / 100	255 ms	34872 KiB

synchronization

#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define MASK(i) ((1)<<(i))
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_asince_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=1e5+1;
int n,t=0,m,q;
vector<int> adj[nmax];
pii edge[nmax];
int jump[nmax][20],tin[nmax],tout[nmax],tree[nmax],pri[nmax],pub[nmax],depth[nmax],st[nmax];

void input()
{
    cin >> n >> m >> q;
    FOR(i,1,n-1)
    {
        cin >> edge[i].fi >> edge[i].se;
        adj[edge[i].fi].push_back(edge[i].se);
        adj[edge[i].se].push_back(edge[i].fi);
    }
}

void update(int x,int val)
{
    while(x<=n)
    {
        tree[x]+=val;
        x+=(x&-x);
    }
}

int get(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=tree[x];
        x-=(x&-x);
    }
    return ans;
}

void pre_dfs(int u,int v)
{
    tin[u]=++t;
    FORD(i,adj[u])
    {
        if(i==v) continue;
        jump[i][0]=u;
        depth[i]=depth[u]+1;
        pre_dfs(i,u);
    }
    tout[u]=t;
}

void build()
{
    FOR(i,1,19) FOR(u,1,n) jump[u][i]=jump[jump[u][i-1]][i-1];
}

int find(int u)
{
    REP(i,19,0)
    {
        int v=jump[u][i];
        if(!jump[u][i]) continue;
        if(get(tin[u])-get(tin[v])==(1<<i)) u=v;
    }
    return u;
}

void solve()
{
    pre_dfs(1,0);
    build();
    FOR(i,1,n) pri[i]=1;
    while(m--)
    {
        int x; cin >> x;
        int u=edge[x].fi;
        int v=edge[x].se;
        if(depth[u]<depth[v]) swap(u,v); // v la cha cua u
        v=find(v);
//        cout << v << ' ' << pri[v] << '\n';
        if(!st[x])
        {
            pri[v]+=pri[u]-pub[u];
            update(tin[u],+1);
            update(tout[u]+1,-1);
        }
        else
        {
            pri[u]=pri[v];
            pub[u]=pri[v];
            update(tin[u],-1);
            update(tout[u]+1,+1);
        }
        st[x]=1-st[x];
    }
    while(q--)
    {
        int i; cin >> i;
        cout << pri[find(i)] << '\n';
    }
}

signed main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

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