Submission #1162667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162667		hahahoang132	동기화 (JOI13_synchronization)	C++20	50 / 100	164 ms	55880 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
using ll = int;
using ld = long double;
const ll N = 5e5 + 5;
const ll mod = 1e9 + 7;
#define bit(x,y) ((x >> y) & 1)
vector<ll> a[N];
ll u[N],v[N];
ll par[N],ch[N],head[N];
set<pair<ll,ll>> haha[N];
ll sz[N],h[N],bc[N];
void build(ll x, ll px)
{
    par[x] = px;
    sz[x] = 1;
    for(auto y : a[x])
    {
        if(y == px) continue;
        h[y] = h[x] + 1;
        build(y,x);
        sz[x] += sz[y];
        if(sz[bc[x]] <= sz[y]) bc[x] = y;
    }
}
void hld(ll x, ll t)
{
    ch[x] = t;
    if(bc[x] != 0) hld(bc[x],t);
}
ll b[N],lz[N];
ll t[N];
ll fp(ll x)
{
    pair<ll,ll> tmp = *(--haha[ch[x]].upper_bound({h[x],x}));
    if(tmp.second == -1) return fp(par[head[ch[x]]]);
    else return tmp.second;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,m,q;
    cin >> n >> m >> q;
    ll i,j;
    for(i = 1;i < n;i++)
    {
        cin >> u[i] >> v[i];
        a[u[i]].push_back(v[i]);
        a[v[i]].push_back(u[i]);
    }
    h[1] = 1;
    build(1,0);
    ll c = 0;
    for(i = 1;i <= n;i++)
    {
        b[i] = lz[i] = 1;
        if(bc[par[i]] != i)
        {
            hld(i,++c);
            head[c] = i;
            haha[c].insert({-1,-1});
        }
        haha[ch[i]].insert({h[i],i});
    }
    for(i = 1;i <= m;i++)
    {
        ll id;
        cin >> id;
        if(h[u[id]] < h[v[id]]) swap(u[id],v[id]);
        ll x = u[id];
        if(t[id] == 0)
        {
            t[id] = 1;
            haha[ch[x]].erase({h[x],x});
            ll px = fp(x);
            b[px] += lz[x];
            lz[px] += lz[x];
            lz[x] = 0;
        }else
        {
            t[id] = 0;
            ll px = fp(x);
            b[x] = b[px];
            haha[ch[x]].insert({h[x],x});
        }
    }
    while(q--)
    {
        ll x;
        cin >> x;
        cout << b[fp(x)] << "\n";
    }
}

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