oj.uz

Submission #171420

# Submission time Handle Problem Language Result Execution time Memory
171420 2019-12-28T16:03:52 Z dolphingarlic Synchronization (JOI13_synchronization) C++14
100 / 100
 494 ms 21380 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

vector<int> g[100001];
pair<int, int> e[200001];
int n, m, q, f[100001], l[100001], t = 1, tin[100001], tout[100001], anc[100001][20], bit[100001];

void dfs(int v = 1, int p = 0) {
    anc[v][0] = p;
    for (int i = 1; i < 20 && anc[v][i - 1]; i++) anc[v][i] = anc[anc[v][i - 1]][i - 1];
    f[v] = 1;
    tin[v] = t++;
    for (int i : g[v]) if (i != p) dfs(i, v);
    tout[v] = t;
}

void up(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }
int qu(int pos) {
    int ans = 0;
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
    return ans;
}

int lca(int v) {
    int lca = v;
    for (int i = 19; ~i; i--) if (anc[lca][i] && qu(tin[anc[lca][i]]) == qu(tin[v])) lca = anc[lca][i];
    return lca;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    FOR(i, 1, n) {
        cin >> e[i].first >> e[i].second;
        g[e[i].first].push_back(e[i].second);
        g[e[i].second].push_back(e[i].first);
    }
    dfs();

    FOR(i, 1, n + 1) {
        up(tin[i], -1);
        up(tout[i], 1);
    }

    while (m--) {
        int x;
        cin >> x;
        int u = e[x].first, v = e[x].second;
        if (anc[u][0] == v) swap(u, v);

        if (lca(v) != v) {
            f[v] = l[v] = f[lca(u)];
            up(tin[v], -1);
            up(tout[v], 1);
        } else {
            f[lca(u)] += f[v] - l[v];
            up(tin[v], 1);
            up(tout[v], -1);
        }
    }

    while (q--) {
        int x;
        cin >> x;
        cout << f[lca(x)] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 21 ms 4216 KB Output is correct
8 Correct 20 ms 4088 KB Output is correct
9 Correct 21 ms 4216 KB Output is correct
10 Correct 314 ms 16608 KB Output is correct
11 Correct 302 ms 16504 KB Output is correct
12 Correct 444 ms 21112 KB Output is correct
13 Correct 190 ms 16748 KB Output is correct
14 Correct 226 ms 16372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 18944 KB Output is correct
2 Correct 146 ms 18424 KB Output is correct
3 Correct 164 ms 20764 KB Output is correct
4 Correct 162 ms 20728 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2684 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 30 ms 4600 KB Output is correct
8 Correct 484 ms 21368 KB Output is correct
9 Correct 483 ms 21372 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 21268 KB Output is correct
2 Correct 227 ms 21252 KB Output is correct
3 Correct 227 ms 21368 KB Output is correct
4 Correct 235 ms 21368 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2684 KB Output is correct
5 Correct 7 ms 2936 KB Output is correct
6 Correct 25 ms 4216 KB Output is correct
7 Correct 424 ms 16888 KB Output is correct
8 Correct 494 ms 21316 KB Output is correct
9 Correct 171 ms 17396 KB Output is correct
10 Correct 239 ms 16960 KB Output is correct
11 Correct 184 ms 19436 KB Output is correct
12 Correct 184 ms 19324 KB Output is correct
13 Correct 224 ms 21380 KB Output is correct