oj.uz

Submission #37878

# Submission time Handle Problem Language Result Execution time Memory
37878 2017-12-28T14:52:36 Z nickyrio Synchronization (JOI13_synchronization) C++14
100 / 100
 346 ms 23888 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 201000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
template<typename T> inline void read(T &x) {
    char c;
    bool neg = false;
    while (!isdigit(c = getchar()) && c != '-');
    x = 0;
    if (c == '-') {
        neg = true;
        c = getchar();
    }
    do {
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    if (neg) x = -x;
}
template<typename T> inline void write(T x) {
    if (x < 0) {
        putchar('-');
        write(-x);return;
    }
    if (x < 10) {
        putchar(char(x + 48));
    }
    else {
        write(x/10);
        putchar(char(48 + x%10));
    }
}
template<typename T> inline void writeln(T x) {
    write(x);
    putchar('\n');
}
using namespace std;

int n, m, q, from[N], to[N], tin[N], tout[N], cntDfs, last[N], res[N], exist[N], pos[N];
vector<int> e[N];
int IT[4 * N];

void dfs(int u, int p) {
    tin[u] = ++cntDfs;
    pos[cntDfs] = u;
    for (int v : e[u]) if (v != p) {
        dfs(v, u);
    }
    tout[u] = cntDfs;
}

void Build(int k, int l, int r) {
    if (l == r) {
        IT[k] = tout[pos[l]];
        res[l] = 1;
        return;
    }
    int m = (l + r) >> 1;
    Build(k << 1, l, m);
    Build(k << 1 | 1, m + 1, r);
    IT[k] = max(IT[k << 1], IT[k << 1 | 1]);
}

void Up(int k, int l, int r, int u, int val) {
    if (l == r) {
        IT[k] = val;return;
    }
    int m = (l + r) >> 1;
    if (u <= m) Up(k << 1, l, m, u, val);
    else Up(k << 1 | 1, m + 1, r, u, val);
    IT[k] = max(IT[k << 1], IT[k << 1 | 1]);
}

int Find(int k, int l, int r, int u, int val) {
    if (l > u || IT[k] < val) return -1;
    if (l == r) return pos[l];
    int m = (l + r) >> 1;
    int x = Find(k << 1 | 1, m + 1, r, u, val);
    if (x != -1) return x;
    return Find(k << 1, l, m, u, val);
} 

int main() {
    IO;
    read(n);read(m);read(q);
    FOR(i, 1, n - 1) {
        read(from[i]);read(to[i]);
        e[from[i]].push_back(to[i]);
        e[to[i]].push_back(from[i]);
    }
    dfs(1, -1);
    FOR(i, 1, n - 1) {
        if (tin[from[i]] > tin[to[i]]) swap(from[i], to[i]);
    }
    Build(1, 1, n);
    int x;
    REP(i, m) {
        read(x);
        int u = from[x], v = to[x];
        int root = Find(1, 1, n, tin[u], tout[u]);
        if (!exist[x]) {
            res[root] += res[v] - last[v];
            Up(1, 1, n, tin[v], 0);
        }
        else {
            last[v] = res[v] = res[root];
            Up(1, 1, n, tin[v], tout[v]);    
        }
        exist[x] ^= 1;
    }
    while (q--) {
        read(x); writeln(res[Find(1, 1, n, tin[x], tout[x])]);
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16152 KB Output is correct
2 Correct 0 ms 16152 KB Output is correct
3 Correct 0 ms 16152 KB Output is correct
4 Correct 3 ms 16152 KB Output is correct
5 Correct 0 ms 16152 KB Output is correct
6 Correct 0 ms 16152 KB Output is correct
7 Correct 9 ms 16548 KB Output is correct
8 Correct 9 ms 16548 KB Output is correct
9 Correct 6 ms 16548 KB Output is correct
10 Correct 296 ms 19452 KB Output is correct
11 Correct 256 ms 19452 KB Output is correct
12 Correct 193 ms 23884 KB Output is correct
13 Correct 156 ms 19868 KB Output is correct
14 Correct 159 ms 19452 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 21816 KB Output is correct
2 Correct 99 ms 21644 KB Output is correct
3 Correct 56 ms 23884 KB Output is correct
4 Correct 69 ms 23876 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16152 KB Output is correct
2 Correct 0 ms 16152 KB Output is correct
3 Correct 0 ms 16152 KB Output is correct
4 Correct 3 ms 16152 KB Output is correct
5 Correct 0 ms 16152 KB Output is correct
6 Correct 0 ms 16152 KB Output is correct
7 Correct 9 ms 16760 KB Output is correct
8 Correct 243 ms 23880 KB Output is correct
9 Correct 263 ms 23884 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 23884 KB Output is correct
2 Correct 109 ms 23852 KB Output is correct
3 Correct 103 ms 23888 KB Output is correct
4 Correct 103 ms 23884 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16152 KB Output is correct
2 Correct 0 ms 16152 KB Output is correct
3 Correct 3 ms 16152 KB Output is correct
4 Correct 0 ms 16152 KB Output is correct
5 Correct 3 ms 16152 KB Output is correct
6 Correct 26 ms 16548 KB Output is correct
7 Correct 346 ms 19452 KB Output is correct
8 Correct 233 ms 23880 KB Output is correct
9 Correct 199 ms 19868 KB Output is correct
10 Correct 219 ms 19452 KB Output is correct
11 Correct 103 ms 21812 KB Output is correct
12 Correct 106 ms 21816 KB Output is correct
13 Correct 99 ms 23880 KB Output is correct