oj.uz

Submission #470279

# Submission time Handle Problem Language Result Execution time Memory
470279 2021-09-03T11:17:21 Z soroush Synchronization (JOI13_synchronization) C++17
100 / 100
 400 ms 35396 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 10;
const int inf = 1e8 + 7;
const int lg = 22;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x, exit(0)
#define ms(x, y) memset(x, y, sizeof x)

int n, m, q, root, tim;
int p[maxn], c[maxn], par[maxn][lg], st[maxn], ft[maxn];
int ans[maxn], lst[maxn], t[maxn];
ll fen[maxn];
int a[maxn];
bool mark[maxn], up[maxn];
vector < int > adj[maxn];

void dfs(int v) {
    st[v] = ++tim;
    for (int i: adj[v]) {
        if (p[i] == par[v][0]) continue;
        if (c[i] == v) swap(c[i], p[i]);
        par[c[i]][0] = v;
        dfs(c[i]);
    }
    ft[v] = tim;
}

void Add(int pos, int x) {
    for (; pos < maxn; pos += pos & -pos) fen[pos] += x;
}

void add(int l, int r, int x) {
    Add(l, x);
    Add(r + 1, -x);
}

int get(int pos) {
    int ans = 0;
    for (; pos; pos -= pos & -pos)
        ans += fen[pos];
    return ans;
}

int getpar(int v) {
    int x = get(st[v]);
    for (int i = lg - 1; ~i; i--)
        if (par[v][i] && (1 << i) == x - get(st[par[v][i]]))
            v = par[v][i], x = get(st[v]);
    return v;
}

struct hld {
    int sz[maxn], st[maxn], ft[maxn], mx[maxn], h[maxn], tim, par[maxn], head[maxn];
    int fen[maxn];
    void dfs(int v, int p = 0) {
        h[v] = h[p] + 1;
        par[v] = p;
        st[v] = ++tim;
        sz[v] = 1;
        for (int i: adj[v])
            if (c[i] ^ v) {
                dfs(c[i], v);
                if (sz[c[i]] >= sz[mx[v]]) mx[v] = c[i];
                sz[v] += sz[c[i]];
            }
        ft[v] = tim;
    }
    void hdfs(int v) {
        st[v] = ++tim;
        if (!head[v]) head[v] = v;
        if (mx[v]) head[mx[v]] = head[v], hdfs(mx[v]);
        for (int i: adj[v])
            if (p[i] == v and c[i] ^ mx[v])
                hdfs(c[i]);
        ft[v] = tim;
    }
    void add(int pos, int x) {
        for (; pos < maxn; pos += pos & -pos)
            fen[pos] += x;
    }
    void add(int l, int r, int x) {
        assert(l <= r);
        add(l, x);
        add(r + 1, -x);
    }
    int get(int v) {
        int ans = 0;
        for (v = st[v]; v; v -= v & -v)
            ans += fen[v];
        return ans;
    }
    void padd(int u, int v, int x) {
        if (!x) return;
        while (head[u] ^ head[v]) {
            add(st[head[u]], st[u], x);
            u = par[head[u]];
        }
        add(st[v], st[u], x);
    }
}
HLD;

int32_t main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        cin >> p[i] >> c[i];
        adj[p[i]].pb(i);
        adj[c[i]].pb(i);
    }
    for (int i = 1; i <= m; i++)
        cin >> t[i], lst[t[i]] = i;
    root = 1;
    dfs(root);
    HLD.dfs(root);
    HLD.hdfs(root);
    for (int j = 1; j < lg; j++)
        for (int i = 1; i <= n; i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    for (int i = 1; i <= n; i++)
        a[i] = 1, HLD.padd(i, i, 1);
    for (int i = 1; i <= m; i++) {
        mark[t[i]] ^= 1;
        int v = c[t[i]];
        up[v] ^= 1;
        if (mark[t[i]]) {
            add(st[v], ft[v], 1);
            a[getpar(v)] += a[v];
            HLD.padd(par[v][0], getpar(v), a[v]);
            a[v] = 0;
        } else {

            ans[v] = ans[getpar(v)] + HLD.get(getpar(v)) - HLD.get(v);

            add(st[v], ft[v], -1);
        }
    }
    for (int i = 1; i <= q; i++) {
        int v;
        cin >> v;
        cout << ans[getpar(v)] + HLD.get(getpar(v)) << endl;
    }
    return (0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5168 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5308 KB Output is correct
7 Correct 20 ms 7316 KB Output is correct
8 Correct 19 ms 7320 KB Output is correct
9 Correct 23 ms 7244 KB Output is correct
10 Correct 295 ms 26884 KB Output is correct
11 Correct 313 ms 26892 KB Output is correct
12 Correct 315 ms 34608 KB Output is correct
13 Correct 176 ms 26344 KB Output is correct
14 Correct 207 ms 25540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 30124 KB Output is correct
2 Correct 129 ms 29848 KB Output is correct
3 Correct 184 ms 33316 KB Output is correct
4 Correct 169 ms 33220 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5188 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5452 KB Output is correct
7 Correct 28 ms 8116 KB Output is correct
8 Correct 400 ms 35356 KB Output is correct
9 Correct 354 ms 35368 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 35396 KB Output is correct
2 Correct 234 ms 34296 KB Output is correct
3 Correct 236 ms 34504 KB Output is correct
4 Correct 222 ms 34476 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 5 ms 5452 KB Output is correct
6 Correct 23 ms 7372 KB Output is correct
7 Correct 312 ms 27656 KB Output is correct
8 Correct 370 ms 35360 KB Output is correct
9 Correct 186 ms 27496 KB Output is correct
10 Correct 283 ms 26880 KB Output is correct
11 Correct 161 ms 31316 KB Output is correct
12 Correct 164 ms 31300 KB Output is correct
13 Correct 224 ms 34416 KB Output is correct