oj.uz

Submission #171381

# Submission time Handle Problem Language Result Execution time Memory
171381 2019-12-28T13:23:26 Z dolphingarlic Synchronization (JOI13_synchronization) C++14
100 / 100
 415 ms 24412 KB 
/*
JOI 2013 Synchronisation
*/

#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;
bool active[100001];
vector<int> graph[100001];
pair<int, int> edges[200001];

int info[100001], last_sync[100001];

// DFS order
int timer = 1, tin[100001], tout[100001];
// Binary lifting parents
int 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] = timer++;
    for (int i : graph[node]) if (i != parent) dfs(i, node);
    tout[node] = timer;
}

// Fenwick tree
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;
}

// Binary lifting
int find_ancestor(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 >> edges[i].first >> edges[i].second;
        graph[edges[i].first].push_back(edges[i].second);
        graph[edges[i].second].push_back(edges[i].first);
    }
    dfs();

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

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

        if (active[x]) {
            info[v] = last_sync[v] = info[find_ancestor(u)];
            update(tin[v], -1);
            update(tout[v], 1);
        } else {
            info[find_ancestor(u)] += info[v] - last_sync[v];
            update(tin[v], 1);
            update(tout[v], -1);
        }
        active[x] = !active[x];
    }

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2808 KB Output is correct
2 Correct 5 ms 2552 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 5 ms 2680 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 17 ms 4344 KB Output is correct
8 Correct 19 ms 4344 KB Output is correct
9 Correct 18 ms 4348 KB Output is correct
10 Correct 272 ms 18916 KB Output is correct
11 Correct 324 ms 18908 KB Output is correct
12 Correct 322 ms 23544 KB Output is correct
13 Correct 125 ms 18928 KB Output is correct
14 Correct 187 ms 17912 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 20888 KB Output is correct
2 Correct 109 ms 20704 KB Output is correct
3 Correct 122 ms 22620 KB Output is correct
4 Correct 120 ms 22520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2772 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 4 ms 2768 KB Output is correct
4 Correct 2 ms 2552 KB Output is correct
5 Correct 4 ms 2684 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 24 ms 4984 KB Output is correct
8 Correct 407 ms 24280 KB Output is correct
9 Correct 374 ms 24316 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 24412 KB Output is correct
2 Correct 204 ms 23780 KB Output is correct
3 Correct 186 ms 23800 KB Output is correct
4 Correct 183 ms 23928 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 5 ms 2808 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 5 ms 2936 KB Output is correct
6 Correct 26 ms 4344 KB Output is correct
7 Correct 323 ms 19960 KB Output is correct
8 Correct 414 ms 24328 KB Output is correct
9 Correct 150 ms 19952 KB Output is correct
10 Correct 254 ms 19192 KB Output is correct
11 Correct 154 ms 22008 KB Output is correct
12 Correct 151 ms 21988 KB Output is correct
13 Correct 187 ms 23772 KB Output is correct