oj.uz

Submission #62088

# Submission time Handle Problem Language Result Execution time Memory
62088 2018-07-27T12:37:56 Z FutymyClone Synchronization (JOI13_synchronization) C++14
100 / 100
 577 ms 69152 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector <int> g[N];
int h[N], st[N], en[N], pos[N], node[4 * N], n, m, q, u[N], v[N], res[N], last[N], state[N];
int cnt = 0;

void input(){
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d %d", &u[i], &v[i]);
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }

    h[1] = 0;
    memset(state, 0, sizeof(state));
    memset(last, 0, sizeof(last));
    fill(res + 1, res + n + 1, 1);
}

void dfs (int u, int p) {
    st[u] = ++cnt;
    pos[st[u]] = u;

    for (int v: g[u]) {
        if (v == p) continue;

        h[v] = h[u] + 1;
        dfs(v, u);
    }

    en[u] = cnt;
}

void init (int i, int l, int r) {
    if (l > r) return;
    if (l == r) {
        node[i] = en[pos[l]];
        return;
    }

    int m = (l + r) >> 1;
    init(i << 1, l, m);
    init(i << 1 | 1, m + 1, r);

    node[i] = max(node[i << 1], node[i << 1 | 1]);
}

void update (int i, int l, int r, int p, int val) {
    if (l == r) {
        if (l == p) node[i] = val;
        return;
    }

    int m = (l + r) >> 1;
    if (p <= m) update(i << 1, l, m, p, val);
    else update(i << 1 | 1, m + 1, r, p, val);

    node[i] = max(node[i << 1], node[i << 1 | 1]);
}

int get (int i, int l, int r, int p, int val) {
    if (l > p || node[i] < val) return -1;
    if (l == r) return pos[l];

    int m = (l + r) >> 1;
    int res = get(i << 1 | 1, m + 1, r, p, val);
    if (res != -1) return res;
    return get(i << 1, l, m, p, val);
}

void solve(){
    while (m--) {
        int id;
        scanf("%d", &id);
        if (h[u[id]] > h[v[id]]) swap(u[id], v[id]);

        int root = get(1, 0, N, st[u[id]], en[u[id]]);
        if (!state[id]) {
            res[root] += res[v[id]] - last[v[id]];
            update(1, 0, N, st[v[id]], -1);
        }
        else {
            res[v[id]] = res[root];
            last[v[id]] = res[root];
            update(1, 0, N, st[v[id]], en[v[id]]);
        }

        state[id] ^= 1;
    }

    while (q--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", res[get(1, 0, N, st[x], en[x])]);
    }
}

int main(){
    input();
    dfs(1, 1);
    init(1, 0, N);
    solve();
    return 0;
}

Compilation message

synchronization.cpp: In function 'void input()':
synchronization.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u[i], &v[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'void solve()':
synchronization.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &id);
         ~~~~~^~~~~~~~~~~
synchronization.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4472 KB Output is correct
2 Correct 8 ms 4592 KB Output is correct
3 Correct 9 ms 4684 KB Output is correct
4 Correct 9 ms 4796 KB Output is correct
5 Correct 9 ms 4920 KB Output is correct
6 Correct 8 ms 4920 KB Output is correct
7 Correct 31 ms 5732 KB Output is correct
8 Correct 30 ms 5840 KB Output is correct
9 Correct 36 ms 6032 KB Output is correct
10 Correct 350 ms 13904 KB Output is correct
11 Correct 364 ms 16092 KB Output is correct
12 Correct 259 ms 22988 KB Output is correct
13 Correct 311 ms 22988 KB Output is correct
14 Correct 243 ms 22988 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 26468 KB Output is correct
2 Correct 141 ms 28416 KB Output is correct
3 Correct 126 ms 32348 KB Output is correct
4 Correct 129 ms 34076 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 34076 KB Output is correct
2 Correct 9 ms 34076 KB Output is correct
3 Correct 9 ms 34076 KB Output is correct
4 Correct 10 ms 34076 KB Output is correct
5 Correct 7 ms 34076 KB Output is correct
6 Correct 10 ms 34076 KB Output is correct
7 Correct 39 ms 34076 KB Output is correct
8 Correct 382 ms 37664 KB Output is correct
9 Correct 373 ms 40496 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 43372 KB Output is correct
2 Correct 162 ms 45992 KB Output is correct
3 Correct 209 ms 48380 KB Output is correct
4 Correct 148 ms 50708 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 50708 KB Output is correct
2 Correct 8 ms 50708 KB Output is correct
3 Correct 10 ms 50708 KB Output is correct
4 Correct 10 ms 50708 KB Output is correct
5 Correct 13 ms 50708 KB Output is correct
6 Correct 45 ms 50708 KB Output is correct
7 Correct 577 ms 50708 KB Output is correct
8 Correct 352 ms 56432 KB Output is correct
9 Correct 285 ms 56432 KB Output is correct
10 Correct 317 ms 57128 KB Output is correct
11 Correct 194 ms 62092 KB Output is correct
12 Correct 174 ms 64816 KB Output is correct
13 Correct 149 ms 69152 KB Output is correct