oj.uz

Submission #547898

# Submission time Handle Problem Language Result Execution time Memory
547898 2022-04-12T01:31:30 Z 8e7 Synchronization (JOI13_synchronization) C++17
100 / 100
 481 ms 23660 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 (!anc[i][head]) continue;
			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 1 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 2776 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 13 ms 4304 KB Output is correct
8 Correct 13 ms 4308 KB Output is correct
9 Correct 12 ms 4180 KB Output is correct
10 Correct 195 ms 16916 KB Output is correct
11 Correct 185 ms 16940 KB Output is correct
12 Correct 453 ms 23032 KB Output is correct
13 Correct 61 ms 17168 KB Output is correct
14 Correct 117 ms 16944 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 20096 KB Output is correct
2 Correct 93 ms 20080 KB Output is correct
3 Correct 99 ms 23068 KB Output is correct
4 Correct 91 ms 23028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 2772 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 25 ms 4920 KB Output is correct
8 Correct 427 ms 23356 KB Output is correct
9 Correct 373 ms 23272 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 23360 KB Output is correct
2 Correct 103 ms 23576 KB Output is correct
3 Correct 111 ms 23648 KB Output is correct
4 Correct 133 ms 23660 KB Output is correct

Subtask #5
40.0 / 40.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 1 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 13 ms 4308 KB Output is correct
7 Correct 233 ms 17260 KB Output is correct
8 Correct 481 ms 23280 KB Output is correct
9 Correct 89 ms 17736 KB Output is correct
10 Correct 157 ms 17644 KB Output is correct
11 Correct 89 ms 20824 KB Output is correct
12 Correct 83 ms 20724 KB Output is correct
13 Correct 112 ms 23660 KB Output is correct