제출 #1370066

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

synchronization

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long 
const int inf = 2e9;

struct Fenwick{
    int n;
    vector<int> fw;
    Fenwick(int _n) : n(_n), fw(_n + 1, 0) {}
    void add(int id, int val) {
        for (;id <= n; id += id & -id)
            fw[id] += val;
    }

    int get(int id) {
        int ans = 0;
        for (; id; id -= id & -id)
            ans += fw[id];
        return ans;
    }

    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<ar<int, 2>> edges(n);
    vector<vector<int>> g(n);
    for (int i = 1; i < n;i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
        edges[i] = {u, v};
    }   

    int timer = 0;
    vector<int> tin(n), tout(n);
    vector<vector<int>> lift(n, vector<int> (20, -1));

    function<void(int, int)> dfs = [&](int u, int p) {
        tin[u] = ++timer;
        lift[u][0] = p;
        for (int i = 1; i < 20;i++) {
            int half = lift[u][i - 1];
            if (half == -1)
                break;
            lift[u][i] = lift[half][i - 1];
        }

        for (int v : g[u]) {
            if (v == p)
                continue;
            dfs(v, u);
        }

        tout[u] = timer;
    }; 

    dfs(0, -1);
    Fenwick fw(timer + 2);
    for (int i = 0; i < n;i++)
        fw.add(tin[i], +1), fw.add(tout[i] + 1, -1);

    vector<int> act(n, 0);
    vector<ll> tot(n, 1), last(n, 0);

    auto find_boss = [&](int x) {
        int ans = x;
        int sum = fw.get(tin[x]);
        for (int i = 19; i >= 0;i--) {
            if (lift[ans][i] == -1)
                continue;
            int sum2 = fw.get(tin[lift[ans][i]]);
            if (sum2 == sum)
                ans = lift[ans][i];
        }
        return ans;
    };

    for (int i = 0; i < m;i++) {
        int x; cin >> x;
        auto [u, p] = edges[x];
        if (lift[u][0] != p)
            swap(u, p);
        
        assert(lift[u][0] == p);
        int boss = find_boss(p);
        if (act[x]) {
            act[x] = 0;
            last[x] = tot[boss];
            tot[u] = tot[boss];
            fw.add(tin[u], +1);
            fw.add(tout[u] + 1, -1);
            continue;
        }

        act[x] = 1;
        tot[boss] = tot[boss] + tot[u] - last[x];
        fw.add(tin[u], -1);
        fw.add(tout[u] + 1, +1);
    }

    while (q--) {
        int x; cin >> x;
        int boss = find_boss(--x);
        cout << tot[boss] << "\n";
    }

}

int32_t main() { 

#ifdef Behruz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif 

    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 20 / 20
• 서브태스크 3: 10 / 10
• 서브태스크 4: 20 / 20
• 서브태스크 5: 40 / 40