oj.uz

Submission #241604

# Submission time Handle Problem Language Result Execution time Memory
241604 2020-06-24T17:26:09 Z kostia244 Synchronization (JOI13_synchronization) C++17
100 / 100
 2474 ms 23384 KB 
//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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 8 ms 4480 KB Output is correct
3 Correct 7 ms 4480 KB Output is correct
4 Correct 7 ms 4480 KB Output is correct
5 Correct 7 ms 4480 KB Output is correct
6 Correct 8 ms 4608 KB Output is correct
7 Correct 39 ms 5932 KB Output is correct
8 Correct 39 ms 5932 KB Output is correct
9 Correct 39 ms 5932 KB Output is correct
10 Correct 2474 ms 17888 KB Output is correct
11 Correct 2359 ms 18020 KB Output is correct
12 Correct 2414 ms 22500 KB Output is correct
13 Correct 2186 ms 17892 KB Output is correct
14 Correct 934 ms 16104 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1408 ms 20068 KB Output is correct
2 Correct 1419 ms 19812 KB Output is correct
3 Correct 871 ms 20644 KB Output is correct
4 Correct 876 ms 20636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 7 ms 4480 KB Output is correct
3 Correct 8 ms 4480 KB Output is correct
4 Correct 8 ms 4480 KB Output is correct
5 Correct 7 ms 4480 KB Output is correct
6 Correct 9 ms 4736 KB Output is correct
7 Correct 49 ms 6568 KB Output is correct
8 Correct 2450 ms 23264 KB Output is correct
9 Correct 2445 ms 23268 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2461 ms 23268 KB Output is correct
2 Correct 906 ms 21736 KB Output is correct
3 Correct 901 ms 21864 KB Output is correct
4 Correct 891 ms 21964 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4480 KB Output is correct
2 Correct 8 ms 4480 KB Output is correct
3 Correct 8 ms 4480 KB Output is correct
4 Correct 7 ms 4480 KB Output is correct
5 Correct 8 ms 4608 KB Output is correct
6 Correct 48 ms 6060 KB Output is correct
7 Correct 2402 ms 18916 KB Output is correct
8 Correct 2454 ms 23384 KB Output is correct
9 Correct 2255 ms 19084 KB Output is correct
10 Correct 950 ms 17428 KB Output is correct
11 Correct 1418 ms 21368 KB Output is correct
12 Correct 1427 ms 21348 KB Output is correct
13 Correct 891 ms 21868 KB Output is correct