oj.uz

Submission #171421

# Submission time Handle Problem Language Result Execution time Memory
171421 2019-12-28T16:05:50 Z dolphingarlic Synchronization (JOI13_synchronization) C++14
100 / 100
 524 ms 21496 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define x first
#define y second
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], c[100001][20], b[100001];

void dfs(int v = 1, int p = 0) {
    c[v][0] = p;
    for (int i = 1; i < 20 && c[v][i - 1]; i++) c[v][i] = c[c[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 p, int val) { for (; p <= n; p += (p & (-p))) b[p] += val; }
int qu(int p) {
    int ans = 0;
    for (; p; p -= (p & (-p))) ans += b[p];
    return ans;
}

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

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

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

    while (m--) {
        int x;
        cin >> x;
        int u = e[x].x, v = e[x].y;
        if (c[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 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2680 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 20 ms 4088 KB Output is correct
8 Correct 21 ms 4088 KB Output is correct
9 Correct 21 ms 4088 KB Output is correct
10 Correct 296 ms 16536 KB Output is correct
11 Correct 367 ms 16504 KB Output is correct
12 Correct 426 ms 21156 KB Output is correct
13 Correct 165 ms 16752 KB Output is correct
14 Correct 201 ms 16120 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 18744 KB Output is correct
2 Correct 154 ms 18424 KB Output is correct
3 Correct 174 ms 20740 KB Output is correct
4 Correct 171 ms 20744 KB Output is correct

Subtask #3
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 2808 KB Output is correct
4 Correct 8 ms 2724 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 491 ms 21384 KB Output is correct
9 Correct 524 ms 21260 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 21292 KB Output is correct
2 Correct 225 ms 21308 KB Output is correct
3 Correct 253 ms 21484 KB Output is correct
4 Correct 224 ms 21496 KB Output is correct

Subtask #5
40.0 / 40.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 2552 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 6 ms 2940 KB Output is correct
6 Correct 24 ms 4216 KB Output is correct
7 Correct 372 ms 16856 KB Output is correct
8 Correct 517 ms 21368 KB Output is correct
9 Correct 168 ms 17392 KB Output is correct
10 Correct 236 ms 16760 KB Output is correct
11 Correct 184 ms 19292 KB Output is correct
12 Correct 184 ms 19332 KB Output is correct
13 Correct 225 ms 21368 KB Output is correct