oj.uz

Submission #1094366

# Submission time Handle Problem Language Result Execution time Memory
1094366 2024-09-29T12:53:28 Z gyg Synchronization (JOI13_synchronization) C++17
100 / 100
 2367 ms 26964 KB 
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vct vector
#define pii pair<int, int>
#define fir first 
#define sec second 
const int MX_N = 1e5 + 5;

int n, m, q;
arr<vct<int>, MX_N> adj;
arr<pii, MX_N> edg;

int nm_inds;
arr<int, MX_N> ind, fn_ind;
arr<arr<int, 20>, MX_N> anc;
void dfs(int u = 1) {
    nm_inds++, ind[u] = nm_inds;
    for (int v : adj[u])
        if (!ind[v]) dfs(v), anc[v][0] = u;
    fn_ind[u] = nm_inds;
}
void prcmp() {
    dfs();
    for (int i = 1; i <= 18; i++)
        for (int u = 1; u <= n; u++)
            anc[u][i] = anc[anc[u][i - 1]][i - 1];
}

arr<int, 4 * MX_N> sgtr;
void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
    if (i < lw || hg < i) return;
    if (lw == hg) { sgtr[u] += x; return; }
    int md = (lw + hg) / 2;
    upd(i, x, 2 * u, lw, md), upd(i, x, 2 * u + 1, md + 1, hg);
    sgtr[u] = sgtr[2 * u] + sgtr[2 * u + 1];
}
int qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
    if (r < lw || hg < l) return 0;
    if (l <= lw && hg <= r) return sgtr[u];
    int md = (lw + hg) / 2;
    return qry(l, r, 2 * u, lw, md) + qry(l, r, 2 * u + 1, md + 1, hg); 
}
void trn_on(int u) { upd(ind[u], -1), upd(fn_ind[u] + 1, +1); }
void trn_off(int u) { upd(ind[u], +1), upd(fn_ind[u] + 1, -1); }
int qry_pth(int u, int v) { return qry(1, ind[v]) - qry(1, ind[u]); } 
int gt_pr(int u) {
    int v = u;
    for (int i = 18; i >= 0; i--)
        if (anc[v][i] != 0 && qry_pth(anc[v][i], u) == 0)
            v = anc[v][i];
    return v;
}

arr<bool, MX_N> on;
arr<int, MX_N> vl, lst;
void ins(int u) {
    assert(u != 1);
    int pr_vl = vl[gt_pr(u)] + vl[gt_pr(anc[u][0])] - lst[u];
    trn_on(u);
    vl[gt_pr(u)] = pr_vl;
}
void dlt(int u) {
    lst[u] = vl[gt_pr(u)];
    trn_off(u);
    vl[gt_pr(u)] = vl[gt_pr(anc[u][0])] = lst[u];
}

int main() {
    // freopen("sync.in", "r", stdin);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        cin >> edg[i].fir >> edg[i].sec;
        adj[edg[i].fir].push_back(edg[i].sec);
        adj[edg[i].sec].push_back(edg[i].fir);
    } 

    prcmp();
    for (int u = 2; u <= n; u++) trn_off(u);
    for (int u = 1; u <= n; u++) vl[u] = 1;

    for (int i = 1; i <= m; i++) {
        int j; cin >> j;
        int u = (anc[edg[j].fir][0] == edg[j].sec) ? edg[j].fir : edg[j].sec;
        
        if (!on[u]) on[u] = true, ins(u);
        else on[u] = false, dlt(u);
        
        // for (int v = 1; v <= n; v++) cout << v << "," << gt_pr(v) << " ";
        // for (int v = 1; v <= n; v++) cout << vl[gt_pr(v)] << " ";
        // cout << endl;
    }

    for (int i = 1; i <= q; i++) {
        int u; cin >> u;
        cout << vl[gt_pr(u)] << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 1 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 6 ms 10332 KB Output is correct
7 Correct 58 ms 10780 KB Output is correct
8 Correct 63 ms 10844 KB Output is correct
9 Correct 64 ms 10840 KB Output is correct
10 Correct 733 ms 20048 KB Output is correct
11 Correct 773 ms 20048 KB Output is correct
12 Correct 1920 ms 26212 KB Output is correct
13 Correct 257 ms 19916 KB Output is correct
14 Correct 434 ms 19284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 20816 KB Output is correct
2 Correct 634 ms 22612 KB Output is correct
3 Correct 792 ms 25424 KB Output is correct
4 Correct 827 ms 25504 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 12 ms 10332 KB Output is correct
7 Correct 152 ms 11356 KB Output is correct
8 Correct 2336 ms 26964 KB Output is correct
9 Correct 2367 ms 26964 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2274 ms 24112 KB Output is correct
2 Correct 1132 ms 26448 KB Output is correct
3 Correct 1154 ms 26708 KB Output is correct
4 Correct 1147 ms 26708 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 1 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 7 ms 10344 KB Output is correct
6 Correct 85 ms 10844 KB Output is correct
7 Correct 1046 ms 20900 KB Output is correct
8 Correct 2231 ms 26940 KB Output is correct
9 Correct 397 ms 21072 KB Output is correct
10 Correct 586 ms 20560 KB Output is correct
11 Correct 824 ms 23956 KB Output is correct
12 Correct 847 ms 23960 KB Output is correct
13 Correct 1154 ms 26708 KB Output is correct