oj.uz

Submission #1069238

# Submission time Handle Problem Language Result Execution time Memory
1069238 2024-08-21T17:58:58 Z Perl32 Synchronization (JOI13_synchronization) C++17
100 / 100
 106 ms 19912 KB 
//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;
        for (int i = 0; i < 2; i++) if (c[i]) c[i]->rev ^= 1;
    }

    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 7 ms 1884 KB Output is correct
8 Correct 7 ms 2008 KB Output is correct
9 Correct 8 ms 1984 KB Output is correct
10 Correct 86 ms 15924 KB Output is correct
11 Correct 85 ms 16164 KB Output is correct
12 Correct 69 ms 19020 KB Output is correct
13 Correct 59 ms 15932 KB Output is correct
14 Correct 63 ms 15556 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15524 KB Output is correct
2 Correct 42 ms 15308 KB Output is correct
3 Correct 36 ms 16848 KB Output is correct
4 Correct 35 ms 16688 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 7 ms 2140 KB Output is correct
8 Correct 99 ms 19912 KB Output is correct
9 Correct 78 ms 19912 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 17092 KB Output is correct
2 Correct 51 ms 19556 KB Output is correct
3 Correct 63 ms 19604 KB Output is correct
4 Correct 64 ms 19708 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 9 ms 2140 KB Output is correct
7 Correct 101 ms 16844 KB Output is correct
8 Correct 81 ms 19912 KB Output is correct
9 Correct 71 ms 17212 KB Output is correct
10 Correct 106 ms 16836 KB Output is correct
11 Correct 60 ms 18608 KB Output is correct
12 Correct 61 ms 18628 KB Output is correct
13 Correct 51 ms 19780 KB Output is correct