oj.uz

Submission #1094361

# Submission time Handle Problem Language Result Execution time Memory
1094361 2024-09-29T12:18:39 Z gyg Synchronization (JOI13_synchronization) C++17
0 / 100
 2281 ms 26368 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, MX_M = 2e5 + 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);
    lst[u] = vl[gt_pr(u)] + vl[gt_pr(anc[u][0])] - lst[u];
    trn_on(u);
    vl[gt_pr(u)] = lst[u];
}
void dlt(int u) {
    int pr_vl = vl[gt_pr(u)];
    trn_off(u);
    vl[gt_pr(u)] = pr_vl, vl[gt_pr(anc[u][0])] = pr_vl;
}

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) << " ";
        // cout << endl;
    }

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 638 ms 22356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2281 ms 26368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Incorrect 2 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -