Submission #1292503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292503		AHOKA	동기화 (JOI13_synchronization)	C++20	100 / 100	393 ms	30580 KiB

synchronization

#include <bits/stdc++.h>

//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
//#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) / 2)
#define lc (2 * id)
#define rc (lc + 1)

const int maxn = 2e5 + 10, maxm = 3e3 + 10, oo = 1e18, lg = 31, sq = 1400, mod = 998244353;

int n, m, q, par[lg][maxn], st[maxn], ft[maxn], h[maxn], sz[maxn], up[maxn], hvy[maxn], lst[maxn], ans[maxn], tmr;

vector<int> adj[maxn];

vector<pii> e;

bool stat[maxn];

void pre_dfs(int v, int p){
    h[v] = h[p] + 1;
    par[0][v] = p;
    for (int b = 1; b < lg;b++)
        par[b][v] = par[b - 1][par[b - 1][v]];
    
    sz[v] = 1;
    for(auto u : adj[v])
        if(u ^ p){
            pre_dfs(u, v);
            sz[v] += sz[u];
            if(sz[u] > sz[hvy[v]])
                hvy[v] = u;
        }
}

void dfs(int v, int p, bool f = 0){
    if (f)
        up[v] = up[p];
    else
        up[v] = v;

    st[v] = ++tmr;

    if(hvy[v]){
        up[hvy[v]] = up[v];
        dfs(hvy[v], v, 1);
    }

    for(auto u : adj[v])
        if((u ^ p) && (u ^ hvy[v]))
            dfs(u, v);

    ft[v] = tmr + 1;
}

int fen[maxn];

void add(int i, int val){
    for (; i < maxn; i += i & -i)
        fen[i] += val;
}
 
int get(int i){
    int res = 0;
    for (; i > 0; i -= i & -i)
        res += fen[i];
    return res;
}

bool check(int v, int p, int f){
    if (up[v] != up[p])
        return 0;
    return ((get(st[v]) - get(st[p] - f)) == (h[v] - (h[p] - f)));
}

int go(int v){
    while(v){
        if (check(v, up[v], 1))
        {
            v = par[0][up[v]];
            continue;
        }

        for (int b = lg - 1; b + 1;b--)
            if(check(v, par[b][v], 0))
                v = par[b][v];

        return v;
    }
    return 1;
}

void solve()
{
    cin >> n >> m >> q;
    for (int i = 1; i < n;i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        e.push_back({u, v});
    }

    pre_dfs(1, 0);
    dfs(1, 0);

    for (int i = 1; i <= n;i++)
        ans[i] = 1;

    for (int i = 0; i < n - 1; i++)
        if (st[e[i].F] < st[e[i].S])
            swap(e[i].F, e[i].S);

    add(1, 1);

    while (m--)
    {
        int i;
        cin >> i;
        auto [v, p] = e[--i];
        if (stat[i])
        {
            p = go(v);
            lst[v] = ans[v] = ans[p];
            add(st[v], -1);
        }
        else{
            add(st[v], 1);
            p = go(v);
            ans[p] += ans[v] - lst[v];
            //cout << v << " " << p << endl;
        }
        stat[i] ^= 1;
    }

    while(q--){
        int v;
        cin >> v;
        cout << ans[go(v)] << "\n";
    }
}

signed main()
{
    threesum;
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

Compilation message (stderr)

synchronization.cpp:20:50: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   20 | const int maxn = 2e5 + 10, maxm = 3e3 + 10, oo = 1e18, lg = 31, sq = 1400, mod = 998244353;
      |                                                  ^~~~

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