oj.uz

Submission #86568

# Submission time Handle Problem Language Result Execution time Memory
86568 2018-11-26T15:31:31 Z DifferentHeaven Synchronization (JOI13_synchronization) C++17
100 / 100
 253 ms 68780 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(){
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    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 6 ms 4472 KB Output is correct
2 Correct 7 ms 4636 KB Output is correct
3 Correct 7 ms 4636 KB Output is correct
4 Correct 6 ms 4828 KB Output is correct
5 Correct 7 ms 4828 KB Output is correct
6 Correct 9 ms 4828 KB Output is correct
7 Correct 25 ms 5448 KB Output is correct
8 Correct 26 ms 5660 KB Output is correct
9 Correct 25 ms 5960 KB Output is correct
10 Correct 253 ms 13612 KB Output is correct
11 Correct 225 ms 15900 KB Output is correct
12 Correct 176 ms 22952 KB Output is correct
13 Correct 215 ms 22952 KB Output is correct
14 Correct 132 ms 22952 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 26296 KB Output is correct
2 Correct 110 ms 28312 KB Output is correct
3 Correct 102 ms 32456 KB Output is correct
4 Correct 97 ms 33976 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33976 KB Output is correct
2 Correct 6 ms 33976 KB Output is correct
3 Correct 6 ms 33976 KB Output is correct
4 Correct 7 ms 33976 KB Output is correct
5 Correct 8 ms 33976 KB Output is correct
6 Correct 8 ms 33976 KB Output is correct
7 Correct 24 ms 33976 KB Output is correct
8 Correct 244 ms 37392 KB Output is correct
9 Correct 221 ms 40284 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 43160 KB Output is correct
2 Correct 173 ms 45684 KB Output is correct
3 Correct 148 ms 48032 KB Output is correct
4 Correct 146 ms 50340 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 50340 KB Output is correct
2 Correct 6 ms 50340 KB Output is correct
3 Correct 7 ms 50340 KB Output is correct
4 Correct 7 ms 50340 KB Output is correct
5 Correct 9 ms 50340 KB Output is correct
6 Correct 26 ms 50340 KB Output is correct
7 Correct 247 ms 50340 KB Output is correct
8 Correct 211 ms 56056 KB Output is correct
9 Correct 205 ms 56056 KB Output is correct
10 Correct 189 ms 56736 KB Output is correct
11 Correct 182 ms 61616 KB Output is correct
12 Correct 186 ms 64324 KB Output is correct
13 Correct 136 ms 68780 KB Output is correct