Submission #37878

#	Time	Username	Problem	Language	Result	Execution time	Memory
37878		nickyrio	Synchronization (JOI13_synchronization)	C++14	100 / 100	346 ms	23888 KiB

synchronization

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40