oj.uz

Submission #963613

# Submission time Handle Problem Language Result Execution time Memory
963613 2024-04-15T11:43:22 Z MisterReaper Synchronization (JOI13_synchronization) C++17
100 / 100
 273 ms 24024 KB 
#include <bits/stdc++.h>
using i64 = long long;

constexpr int maxN = 1E5 + 5;
constexpr int L = 20;

std::vector<int> adj[maxN];
int par[maxN][L], tin[maxN], tout[maxN], info[maxN], lastsync[maxN];
int X[maxN], Y[maxN];
bool active[maxN];

int tree[maxN * 2];
struct fenwick {
    int n;
    fenwick(int _n) : n(_n + 1) {}
    void modify(int p, int v) {
        for(++p; p <= n; p += p & -p) {
            tree[p] += v;
        }
    }
    int query(int p) {
        int res = 0;
        for(++p; p > 0; p -= p & -p) {
            res += tree[p];
        }
        return res;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M, Q;
    std::cin >> N >> M >> Q;

    for(int i = 0; i < N - 1; i++) {
        std::cin >> X[i] >> Y[i];
        --X[i], --Y[i];
        adj[X[i]].emplace_back(Y[i]);
        adj[Y[i]].emplace_back(X[i]);
    }

    int t = 0;
    auto dfs = [&](auto&& self, int v) -> void {
        tin[v] = t++;
        info[v] = 1;
        for(int u : adj[v]) {
            if(u == par[v][0]) {
                continue;
            }
            par[u][0] = v;
            self(self, u);
        }
        tout[v] = t++;
    };

    dfs(dfs, 0);

    for(int lg = 1; lg < L; lg++) {
        for(int v = 0; v < N; v++) {
            par[v][lg] = par[par[v][lg - 1]][lg - 1];
        }
    }

    fenwick fen(2 * N);
    for(int i = 0; i < N; i++) {
        fen.modify(tin[i], -1);
        fen.modify(tout[i], 1);
    }

    auto get = [&](int v) -> int {
        for(int lg = L - 1; lg >= 0; lg--) {
            if(fen.query(tin[par[v][lg]]) == fen.query(tin[v])) {
                v = par[v][lg];
            }
        }
        return v;
    };

    for(int i = 0; i < M; i++) {
        int D;
        std::cin >> D;
        --D;
        int u = X[D], v = Y[D];
        if(par[u][0] == v) {
            std::swap(u, v);
        }

        // std::cerr << u << ' ' << v << '\n';
        if(active[D]) {
            info[v] = lastsync[D] = info[get(u)];
            fen.modify(tin[v], -1);
            fen.modify(tout[v], 1);
        } else {
            int newval = info[get(u)] + info[v] - lastsync[D];
            info[get(u)] = newval;
            fen.modify(tin[v], 1);
            fen.modify(tout[v], -1);
        }
        active[D] = !active[D];
        // for(int w = 0; w < N; w++) {
        //     std::cerr << get(w) << " \n"[w + 1 == N];
        // }
        // for(int w = 0; w < 2 * N; w++) {
        //     std::cerr << fen.query(w) << " \n"[w + 1 == 2 * N];
        // }
        // for(int w = 0; w < N; w++) {
        //     std::cerr << info[get(w)] << " \n"[w + 1 == N];
        // }
    }

    for(int i = 0; i < Q; i++) {
        int C;
        std::cin >> C;
        --C;
        std::cout << info[get(C)] << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7520 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 13 ms 8120 KB Output is correct
8 Correct 12 ms 8040 KB Output is correct
9 Correct 16 ms 8128 KB Output is correct
10 Correct 177 ms 19224 KB Output is correct
11 Correct 183 ms 19248 KB Output is correct
12 Correct 202 ms 23128 KB Output is correct
13 Correct 86 ms 19284 KB Output is correct
14 Correct 100 ms 18772 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 21084 KB Output is correct
2 Correct 80 ms 21072 KB Output is correct
3 Correct 80 ms 22700 KB Output is correct
4 Correct 84 ms 22700 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7520 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Correct 3 ms 7512 KB Output is correct
7 Correct 17 ms 8540 KB Output is correct
8 Correct 273 ms 23900 KB Output is correct
9 Correct 220 ms 23992 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 23900 KB Output is correct
2 Correct 145 ms 23636 KB Output is correct
3 Correct 154 ms 24024 KB Output is correct
4 Correct 141 ms 23844 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 21 ms 8024 KB Output is correct
7 Correct 200 ms 20152 KB Output is correct
8 Correct 221 ms 23900 KB Output is correct
9 Correct 119 ms 20428 KB Output is correct
10 Correct 118 ms 20240 KB Output is correct
11 Correct 112 ms 22336 KB Output is correct
12 Correct 106 ms 22244 KB Output is correct
13 Correct 132 ms 23632 KB Output is correct