oj.uz

Submission #171419

# Submission time Handle Problem Language Result Execution time Memory
171419 2019-12-28T16:01:34 Z dolphingarlic Synchronization (JOI13_synchronization) C++14
100 / 100
 529 ms 21496 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m, q;
vector<int> graph[100001];
pair<int, int> e[200001];

int info[100001], last[100001], t = 1, tin[100001], tout[100001], anc[100001][20];

void dfs(int node = 1, int parent = 0) {
    anc[node][0] = parent;
    for (int i = 1; i < 20 && anc[node][i - 1]; i++) anc[node][i] = anc[anc[node][i - 1]][i - 1];
    info[node] = 1;
    tin[node] = t++;
    for (int i : graph[node]) if (i != parent) dfs(i, node);
    tout[node] = t;
}

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

int lca(int node) {
    int lca = node;
    for (int i = 19; ~i; i--) if (anc[lca][i] && query(tin[anc[lca][i]]) == query(tin[node])) 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;
        graph[e[i].first].push_back(e[i].second);
        graph[e[i].second].push_back(e[i].first);
    }
    dfs();

    FOR(i, 1, n + 1) {
        update(tin[i], -1);
        update(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) {
            info[v] = last[v] = info[lca(u)];
            update(tin[v], -1);
            update(tout[v], 1);
        } else {
            info[lca(u)] += info[v] - last[v];
            update(tin[v], 1);
            update(tout[v], -1);
        }
    }

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 2676 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 23 ms 4260 KB Output is correct
8 Correct 21 ms 4216 KB Output is correct
9 Correct 21 ms 4088 KB Output is correct
10 Correct 315 ms 16552 KB Output is correct
11 Correct 302 ms 16632 KB Output is correct
12 Correct 409 ms 21232 KB Output is correct
13 Correct 136 ms 16748 KB Output is correct
14 Correct 207 ms 16192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 18652 KB Output is correct
2 Correct 149 ms 18568 KB Output is correct
3 Correct 166 ms 20856 KB Output is correct
4 Correct 161 ms 20728 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 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 31 ms 4600 KB Output is correct
8 Correct 503 ms 21292 KB Output is correct
9 Correct 529 ms 21288 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 21240 KB Output is correct
2 Correct 225 ms 21272 KB Output is correct
3 Correct 231 ms 21496 KB Output is correct
4 Correct 227 ms 21368 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 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 25 ms 4088 KB Output is correct
7 Correct 406 ms 16888 KB Output is correct
8 Correct 483 ms 21240 KB Output is correct
9 Correct 168 ms 17392 KB Output is correct
10 Correct 237 ms 16860 KB Output is correct
11 Correct 183 ms 19364 KB Output is correct
12 Correct 200 ms 19292 KB Output is correct
13 Correct 236 ms 21368 KB Output is correct