Submission #1069235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069235		Perl32	Synchronization (JOI13_synchronization)	C++17	20 / 100	90 ms	19768 KiB

synchronization

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

typedef struct snode* sn;
struct snode {
    sn p, c[2];
    bool rev = 0;
    int id;

    snode(int i) : id(i) {
        p = c[0] = c[1] = NULL;
    }

    int dir() {
        if (!p) return -2;
        for (int i = 0; i < 2; ++i) {
            if (p->c[i] == this) return i;
        }
        return -1;
    }

    void push() {
        if (!rev) return;
        swap(c[0], c[1]);
        rev = 0;
    }

    bool isRoot() { return dir() < 0; }

    friend void sl(sn x, sn y, int d) {
        if (y) y->p = x;
        if (d >= 0) x->c[d] = y;
    }

    void rot() {
        int x = dir();
        sn pa = p;
        sl(pa->p, this, pa->dir());
        sl(pa, c[x ^ 1], x);
        sl(this, pa, x ^ 1);
    }

    void splay() {
        while (!isRoot() && !p->isRoot()) {
            p->p->push(), p->push(), push();
            if (dir() == p->dir()) {
                p->rot();
            } else {
                rot();
            }
            rot();
        }
        if (!isRoot()) {
            p->push();
            push();
            rot();
        }
        push();
    }

    void expose() {
        for (sn v = this, pre = NULL; v; v = v->p) {
            v->splay();
            v->c[1] = pre;
            pre = v;
        }
        splay();
    }

    void reroot() {
        expose();
        rev ^= 1;
        expose();
    }

    sn gr() {
        expose();
        sn a = this;
        while (a->c[0]) a = a->c[0], a->push();
        a->expose();
        return a;
    }

    friend void link(sn x, sn y) {
        y->reroot();
        x->expose();
        sl(y, x, 0);
    }

    friend void cut(sn x, sn y) {
        sn old = x->gr();
        x->reroot();
        y->expose();
        y->c[0]->p = NULL;
        y->c[0] = NULL;
        old->reroot();
    }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;
    vector<sn> lct(n);
    for (int i = 0; i < n; ++i) lct[i] = new snode(i);
    vector<pair<int, int>> e;
    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);
        e.push_back({u, v});
    }
    vector<int> par(n, -1);
    auto Dfs = [&](auto&& self, int u) -> void {
        for (auto to : g[u]) {
            if (to == par[u]) continue;
            par[to] = u;
            self(self, to);
        }
    };
    Dfs(Dfs, 0);
    for (int i = 0; i < n - 1; ++i) {
        auto& [u, v] = e[i];
        if (par[u] == v) swap(u, v);
    }
    vector<int> used(n - 1, 0), ans(n, 1), lst(n - 1, 0);
    while (m--) {
        int i;
        cin >> i;
        --i;
        auto [p, u] = e[i];
        if (!used[i]) {
            sn x = lct[p]->gr();
            int nw = ans[lct[u]->gr()->id];
            ans[x->id] += nw - lst[i];
            link(lct[p], lct[u]);
        } else {
            sn aboba = lct[u]->gr();
            ans[u] = ans[aboba->id];
            lst[i] = ans[u];
            cut(lct[p], lct[u]);
        }
        used[i] ^= 1;
    }
    while (q--) {
        int x;
        cin >> x;
        cout << ans[lct[--x]->gr()->id] << '\n';
    }
    return 0;
}

/*

 */

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