제출 #470279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470279		soroush	동기화 (JOI13_synchronization)	C++17	100 / 100	400 ms	35396 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 10;
const int inf = 1e8 + 7;
const int lg = 22;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x, exit(0)
#define ms(x, y) memset(x, y, sizeof x)

int n, m, q, root, tim;
int p[maxn], c[maxn], par[maxn][lg], st[maxn], ft[maxn];
int ans[maxn], lst[maxn], t[maxn];
ll fen[maxn];
int a[maxn];
bool mark[maxn], up[maxn];
vector < int > adj[maxn];

void dfs(int v) {
    st[v] = ++tim;
    for (int i: adj[v]) {
        if (p[i] == par[v][0]) continue;
        if (c[i] == v) swap(c[i], p[i]);
        par[c[i]][0] = v;
        dfs(c[i]);
    }
    ft[v] = tim;
}

void Add(int pos, int x) {
    for (; pos < maxn; pos += pos & -pos) fen[pos] += x;
}

void add(int l, int r, int x) {
    Add(l, x);
    Add(r + 1, -x);
}

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

int getpar(int v) {
    int x = get(st[v]);
    for (int i = lg - 1; ~i; i--)
        if (par[v][i] && (1 << i) == x - get(st[par[v][i]]))
            v = par[v][i], x = get(st[v]);
    return v;
}

struct hld {
    int sz[maxn], st[maxn], ft[maxn], mx[maxn], h[maxn], tim, par[maxn], head[maxn];
    int fen[maxn];
    void dfs(int v, int p = 0) {
        h[v] = h[p] + 1;
        par[v] = p;
        st[v] = ++tim;
        sz[v] = 1;
        for (int i: adj[v])
            if (c[i] ^ v) {
                dfs(c[i], v);
                if (sz[c[i]] >= sz[mx[v]]) mx[v] = c[i];
                sz[v] += sz[c[i]];
            }
        ft[v] = tim;
    }
    void hdfs(int v) {
        st[v] = ++tim;
        if (!head[v]) head[v] = v;
        if (mx[v]) head[mx[v]] = head[v], hdfs(mx[v]);
        for (int i: adj[v])
            if (p[i] == v and c[i] ^ mx[v])
                hdfs(c[i]);
        ft[v] = tim;
    }
    void add(int pos, int x) {
        for (; pos < maxn; pos += pos & -pos)
            fen[pos] += x;
    }
    void add(int l, int r, int x) {
        assert(l <= r);
        add(l, x);
        add(r + 1, -x);
    }
    int get(int v) {
        int ans = 0;
        for (v = st[v]; v; v -= v & -v)
            ans += fen[v];
        return ans;
    }
    void padd(int u, int v, int x) {
        if (!x) return;
        while (head[u] ^ head[v]) {
            add(st[head[u]], st[u], x);
            u = par[head[u]];
        }
        add(st[v], st[u], x);
    }
}
HLD;

int32_t main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        cin >> p[i] >> c[i];
        adj[p[i]].pb(i);
        adj[c[i]].pb(i);
    }
    for (int i = 1; i <= m; i++)
        cin >> t[i], lst[t[i]] = i;
    root = 1;
    dfs(root);
    HLD.dfs(root);
    HLD.hdfs(root);
    for (int j = 1; j < lg; j++)
        for (int i = 1; i <= n; i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    for (int i = 1; i <= n; i++)
        a[i] = 1, HLD.padd(i, i, 1);
    for (int i = 1; i <= m; i++) {
        mark[t[i]] ^= 1;
        int v = c[t[i]];
        up[v] ^= 1;
        if (mark[t[i]]) {
            add(st[v], ft[v], 1);
            a[getpar(v)] += a[v];
            HLD.padd(par[v][0], getpar(v), a[v]);
            a[v] = 0;
        } else {

            ans[v] = ans[getpar(v)] + HLD.get(getpar(v)) - HLD.get(v);

            add(st[v], ft[v], -1);
        }
    }
    for (int i = 1; i <= q; i++) {
        int v;
        cin >> v;
        cout << ans[getpar(v)] + HLD.get(getpar(v)) << endl;
    }
    return (0);
}

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