Submission #241604

#	Time	Username	Problem	Language	Result	Execution time	Memory
241604		kostia244	Synchronization (JOI13_synchronization)	C++17	100 / 100	2474 ms	23384 KiB

synchronization

//This is a fucking meme. I hope the intended solution is not this
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,sse,sse2,ssse3,sse4.1,sse4.2,popcnt,tune=native")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
const int maxn = 1<<17;

int n, m, q, sz[maxn], tin[maxn], h[maxn], head[maxn], idx[maxn], p[maxn], ans[maxn], timer = 0;
vector<int> g[maxn], ord;
vector<array<int, 2>> edges;
vector<array<int, 3>> ops;
int tree[maxn*2];


void toggle(int p) {
	for(tree[p+=n] ^= 1; p>>=1;) tree[p] = min(tree[p<<1], tree[p<<1|1]);
}
int get(int l, int r) {
	int a = 1;
	for(l += n, r += n + 1; l < r; l>>=1, r>>=1) {
		if(l&1) a = min(a, tree[l++]);
		if(r&1) a = min(tree[--r], a);
	}
	return a;
}


void dfs(int v) {
	sz[v] = 1;
	for(auto &i : g[v]) {
		g[i].erase(find(all(g[i]), v));
		p[i] = v;
		h[i] = h[v] + 1;
		dfs(i);
		sz[v] += sz[i];
		if(sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
	}
	ord.pb(v);
}
void hld(int v) {
	idx[timer] = v;
	tin[v] = timer++;
	for(auto &i : g[v]) {
		head[i] = g[v][0] == i ? head[v] : i;
		hld(i);
	}
}



int getpar(int v) {
	while(get(tin[head[v]], tin[v]) == 1) v = p[head[v]];
	int i = tin[v], l = tin[head[v]];
	for(int z = 1<<17; z>>=1;)
		if(i-z >= l && get(i-z, i) == 1) {
			i-=z;
		}
	i -= get(i, i);
	return idx[i];
}

int finalpar[maxn];
void find(int v) {
	if(get(tin[v], tin[v])) finalpar[v] = finalpar[p[v]];
	else finalpar[v] = v;
	for(auto &i : g[v])
		find(i);
}
ll val[maxn];
	

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> q;
	edges.resize(n-1);
	for(auto &i : edges) cin >> i[0] >> i[1];
	for(auto [f, t] : edges) {
		g[f].pb(t);
		g[t].pb(f);
	}
	dfs(1);
	head[1] = 1;
	hld(1);
	for(auto &i : edges) if(h[i[0]] < h[i[1]]) swap(i[0], i[1]);
	for(int i; m--;) {
		cin >> i;
		auto [l, h] = edges[i-1];
		int P = getpar(h);
		ops.pb({get(tin[l], tin[l]), l, P});
		toggle(tin[l]);
	}
	
	find(1);
	
	for(int b = 0; b*64 < n; b++) {
		memset(val, 0, sizeof val);
		for(int k = 0; k < 64 && 64*b + k < n; k++) val[64*b + k + 1] = 1ll<<k;
		//for(int i = 1; i <= n; i++) cout << val[i] << " "; cout << '\n';
		for(auto [tp, v, rt] : ops) {
			if(tp) val[v] = val[rt];
			else val[rt] |= val[v];
		}
		for(int i = 1; i <= n; i++) ans[i] += __builtin_popcountll(val[finalpar[i]]);
	}
	
	for(int i; q--;) cin >> i, cout << ans[i] << '\n';
	return 0;
}

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