Submission #306346

#	Time	Username	Problem	Language	Result	Execution time	Memory
306346		syy	Synchronization (JOI13_synchronization)	C++17	100 / 100	313 ms	30240 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i = (int)a; i <= (int)b; i++)
#define DEC(i, a, b) for(int i = (int)a; i >= (int)b; i--)
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
#define f first
#define s second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<pii> vpii;
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define INF (int) 1e9 + 100
#define LLINF (ll) 1e18
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int n, m, q, a, b, p[100005], heavy[100005], head[100005], pos[100005], depth[100005];
int sz[100005], inter[100005], id[100005];
set<int> broken[100005];
vi adj[100005];
vpi edges;
bool state[100005];

int dfs(int x, int par) {
    p[x] = par;
    int sz = 1; //Total size
    int maxchild = 0; //Biggest child
    for (auto it:adj[x]) {
        if (it == par) continue;
        depth[it] = depth[x] + 1;
        int childsize = dfs(it, x); //size at child
        sz += childsize;
        if (childsize > maxchild) {
            maxchild = childsize;
            heavy[x] = it;
            // Stores the heavy child of node x
        }
    }
    return sz;
}

int coun = 1;
void decompose(int x, int h) {
    //coun is the global counter that stores the indices
    head[x] = h;
    pos[x] = coun++;
    id[pos[x]] = x;
    broken[h].insert(pos[x]);
    if (heavy[x] != -1) decompose(heavy[x], h);
    for (auto it:adj[x]) {
        if (it == p[x]) continue;
        if (it == heavy[x]) continue;
        decompose(it, it);
    }
}

int leader(int x) {
    while (broken[head[x]].empty() or *broken[head[x]].begin() > pos[x]) x = p[head[x]];
	auto it = broken[head[x]].upper_bound(pos[x]);
	return id[*(--it)];
}

int main() {
	fastio; cin >> n >> m >> q;
	edges.pb(pi(0, 0));
	FOR(i, 1, n-1) {
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
		edges.pb(pi(a, b));
	}
	memset(heavy, -1, sizeof heavy);
	dfs(1, -1); decompose(1, 1);
	FOR(i, 1, n) sz[i] = 1;
	while (m--) {
		int t; cin >> t;
		a = edges[t].f, b = edges[t].s;
		if (depth[a] < depth[b]) swap(a, b);
		if (state[t]) { //removing edge
			sz[a] = sz[leader(b)];
			inter[a] = sz[a];
			broken[head[a]].insert(pos[a]);
		} else { //adding edge
			int bl = leader(b);
			sz[bl] += sz[a] - inter[a];
			sz[a] = sz[bl];
			broken[head[a]].erase(pos[a]);
		}
		state[t] = !state[t];
	}
	while (q--) {
		cin >> a;
		cout << sz[leader(a)] << "\n";
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40