oj.uz

Submission #171422

# Submission time Handle Problem Language Result Execution time Memory
171422 2019-12-28T16:07:27 Z dolphingarlic Synchronization (JOI13_synchronization) C++14
100 / 100
 952 ms 23928 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;
const int N = 200001;
vector<int> g[N];
pair<int, int> e[N];
int n, m, q, f[N], l[N], t = 1, tin[N], tout[N], c[N][20], b[N];
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;
}
main() {
    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';
    }
}

Compilation message

synchronization.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 4988 KB Output is correct
6 Correct 9 ms 5232 KB Output is correct
7 Correct 38 ms 6392 KB Output is correct
8 Correct 37 ms 6392 KB Output is correct
9 Correct 37 ms 6392 KB Output is correct
10 Correct 501 ms 18912 KB Output is correct
11 Correct 518 ms 18912 KB Output is correct
12 Correct 656 ms 23548 KB Output is correct
13 Correct 340 ms 19184 KB Output is correct
14 Correct 360 ms 18552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 21020 KB Output is correct
2 Correct 292 ms 20856 KB Output is correct
3 Correct 283 ms 23160 KB Output is correct
4 Correct 286 ms 23156 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 12 ms 5112 KB Output is correct
5 Correct 8 ms 5112 KB Output is correct
6 Correct 12 ms 5240 KB Output is correct
7 Correct 76 ms 7032 KB Output is correct
8 Correct 927 ms 23684 KB Output is correct
9 Correct 938 ms 23928 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 23800 KB Output is correct
2 Correct 644 ms 23600 KB Output is correct
3 Correct 649 ms 23716 KB Output is correct
4 Correct 654 ms 23800 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 12 ms 5240 KB Output is correct
6 Correct 71 ms 6392 KB Output is correct
7 Correct 857 ms 19304 KB Output is correct
8 Correct 952 ms 23808 KB Output is correct
9 Correct 636 ms 19872 KB Output is correct
10 Correct 663 ms 19192 KB Output is correct
11 Correct 638 ms 21832 KB Output is correct
12 Correct 633 ms 21880 KB Output is correct
13 Correct 651 ms 23800 KB Output is correct