제출 #1345689

#제출 시각아이디문제언어결과실행 시간메모리
1345689iamhereforfun동기화 (JOI13_synchronization)C++20
100 / 100
270 ms26832 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e6 + 5;
const int M = 1e6 + 5;
const int K = 19;
const int LG = 21;
const long long INF = 1e18 + 5;
const int C = 26;
const int B = 1000;
const int MOD = 998244353;

struct Fenwick
{
    vector<int> ft;
    int n;
    Fenwick(int len)
    {
        n = len;
        ft.assign(n + 1, 0);
    }
    void update(int pos, int val)
    {
        while (pos <= n)
        {
            ft[pos] += val;
            pos += LSOne(pos);
        }
    }
    int get(int pos)
    {
        int sum = 0;
        while (pos > 0)
        {
            sum += ft[pos];
            pos -= LSOne(pos);
        }
        return sum;
    }
    int get(int l, int r)
    {
        return get(r) - get(l - 1);
    }
} ft(N);

int n, m, q, cid, st[N], en[N], binlift[LG][N], ans[N], pre[N], id[N];
vector<pair<int, int>> adj[N];
bool chk[N];

void dfs1(int c, int p)
{
    st[c] = cid++;
    for (auto [i, j] : adj[c])
    {
        if (i == p)
            continue;
        id[j] = i;
        binlift[0][i] = c;
        for (int x = 1; x < LG; x++)
        {
            binlift[x][i] = binlift[x - 1][binlift[x - 1][i]];
        }
        dfs1(i, c);
    }
    en[c] = cid - 1;
}

int getRoot(int i)
{
    // cout << i << "\n";
    for (int x = LG - 1; x >= 0; x--)
    {
        if (binlift[x][i] == 0)
            continue;
        if (ft.get(st[i]) - ft.get(st[binlift[x][i]]) == (1 << x))
        {
            // cout << ft.get(st[i]) << " " << ft.get(st[binlift[x][i]]) << "\n";
            // cout << st[i] << " " << st[binlift[x][i]] << " " << (1 << x) << "\n";
            i = binlift[x][i];
        }
    }
    // cout << i << "\n";
    return i;
}

inline void solve()
{
    cin >> n >> m >> q;
    for (int x = 1; x <= n; x++)
    {
        ans[x] = 1;
    }
    for (int x = 1; x <= n - 1; x++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, x});
        adj[b].push_back({a, x});
    }
    cid = 1;
    dfs1(1, 0);
    for (int x = 1; x <= m; x++)
    {
        int i;
        cin >> i;
        i = id[i];
        // cout << i << " " << getRoot(i) << "\n";
        if (!chk[i])
        {
            chk[i] = 1;
            ft.update(st[i], 1);
            ft.update(en[i] + 1, -1);
            ans[getRoot(i)] += ans[i] - pre[i];
        }
        else
        {
            chk[i] = 0;
            pre[i] = ans[i] = ans[getRoot(i)];
            ft.update(st[i], -1);
            ft.update(en[i] + 1, 1);
        }
    }
    for (int x = 1; x <= q; x++)
    {
        int i;
        cin >> i;
        cout << ans[getRoot(i)] << "\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...