oj.uz

Submission #547893

# Submission time Handle Problem Language Result Execution time Memory
547893 2022-04-12T01:29:22 Z 8e7 Synchronization (JOI13_synchronization) C++17
100 / 100
 461 ms 26204 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct BIT{
	int bit[maxn*2];
	void modify(int ind, int val) {
		ind++;
		for (;ind < maxn*2;ind += ind & (-ind)) bit[ind] += val;
	}
	int query(int ind) {
		ind++;
		int ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
} bit;
vector<int> adj[maxn];
pii ed[maxn];
int anc[17][maxn], dep[maxn], comp[maxn], lef[maxn*2], rig[maxn*2];
int ans[maxn], dif[maxn];
vector<int> ord;
int ti = 1;
void dfs(int n, int par, int d) {
	anc[0][n] = par;
	dep[n] = d;
	ord.push_back(n);
	lef[n] = ti++;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d+1);
		}
	}
	rig[n] = ti++;
}
int jump(int a, int x) {
	int cnt = 0;
	while (x) {
		if (x & 1) a = anc[cnt][a];
		x >>= 1;
	}
	return a;
}

int main() {
	io
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1;i <= n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		ed[i] = {u, v};
	}	
	dfs(1, 0, 0);			
	for (int i = 1;i < 17;i++) {
		for (int j = 1;j <= n;j++) anc[i][j] = anc[i-1][anc[i-1][j]];
	}
	for (int i = 1;i <= n - 1;i++) {
		if (dep[ed[i].ff] > dep[ed[i].ss]) swap(ed[i].ff, ed[i].ss);
	}	
	for (int i = 1;i <= n;i++) {
		bit.modify(lef[i], 1), bit.modify(rig[i], -1);
		comp[i] = 1;
		dif[i] = 1;
		ans[i] = 1;
	}
	while (m--) {
		int id;
		cin >> id;
		int u = ed[id].ff, v = ed[id].ss;
		int head = u, sum = bit.query(lef[u]);
		for (int i = 16;i >= 0;i--) {
			if (bit.query(lef[anc[i][head]]) == sum) {
				head = anc[i][head];
			}	
		}
		//debug(head, v, sum);
		if (comp[v]) {
			dif[head] += dif[v];
			ans[head] += dif[v];
			bit.modify(lef[v], -1);
			bit.modify(rig[v], 1);
			dif[v] = 0;
			comp[v] = 0;
		} else {
			dif[v] = 0;
			ans[v] = ans[head];	
			bit.modify(lef[v], 1);
			bit.modify(rig[v], -1);
			comp[v] = 1;
		}
	}	
	for (int i:ord) {
		if (!comp[i]) ans[i] = ans[anc[0][i]];
	}
	while (q--) {
		int x; cin >> x;
		cout << ans[x] << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2944 KB Output is correct
7 Correct 20 ms 4436 KB Output is correct
8 Correct 19 ms 4420 KB Output is correct
9 Correct 16 ms 4488 KB Output is correct
10 Correct 362 ms 19284 KB Output is correct
11 Correct 366 ms 19288 KB Output is correct
12 Correct 437 ms 25456 KB Output is correct
13 Correct 85 ms 19196 KB Output is correct
14 Correct 191 ms 18648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 20164 KB Output is correct
2 Correct 102 ms 22036 KB Output is correct
3 Correct 91 ms 24764 KB Output is correct
4 Correct 91 ms 24824 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2728 KB Output is correct
2 Correct 2 ms 2808 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2808 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 20 ms 5164 KB Output is correct
8 Correct 406 ms 26200 KB Output is correct
9 Correct 434 ms 26204 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 23364 KB Output is correct
2 Correct 111 ms 25924 KB Output is correct
3 Correct 116 ms 26008 KB Output is correct
4 Correct 111 ms 25976 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 2 ms 2808 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 21 ms 4544 KB Output is correct
7 Correct 394 ms 20072 KB Output is correct
8 Correct 461 ms 26204 KB Output is correct
9 Correct 98 ms 20292 KB Output is correct
10 Correct 254 ms 19924 KB Output is correct
11 Correct 118 ms 23492 KB Output is correct
12 Correct 113 ms 23392 KB Output is correct
13 Correct 121 ms 25976 KB Output is correct