oj.uz

Submission #547896

# Submission time Handle Problem Language Result Execution time Memory
547896 2022-04-12T01:30:44 Z 8e7 Synchronization (JOI13_synchronization) C++17
100 / 100
 493 ms 23976 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 = __lg(dep[u] + 1);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 2812 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 2900 KB Output is correct
7 Correct 15 ms 4436 KB Output is correct
8 Correct 13 ms 4468 KB Output is correct
9 Correct 13 ms 4352 KB Output is correct
10 Correct 192 ms 17160 KB Output is correct
11 Correct 150 ms 17080 KB Output is correct
12 Correct 493 ms 23232 KB Output is correct
13 Correct 65 ms 17436 KB Output is correct
14 Correct 103 ms 17164 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 20476 KB Output is correct
2 Correct 79 ms 20196 KB Output is correct
3 Correct 93 ms 23280 KB Output is correct
4 Correct 94 ms 23284 KB Output is correct

Subtask #3
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 2764 KB Output is correct
6 Correct 3 ms 2944 KB Output is correct
7 Correct 20 ms 5112 KB Output is correct
8 Correct 488 ms 23532 KB Output is correct
9 Correct 460 ms 23576 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 23492 KB Output is correct
2 Correct 113 ms 23872 KB Output is correct
3 Correct 112 ms 23876 KB Output is correct
4 Correct 107 ms 23956 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 3 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 14 ms 4436 KB Output is correct
7 Correct 167 ms 17512 KB Output is correct
8 Correct 476 ms 23492 KB Output is correct
9 Correct 78 ms 18012 KB Output is correct
10 Correct 118 ms 17888 KB Output is correct
11 Correct 107 ms 20948 KB Output is correct
12 Correct 97 ms 21012 KB Output is correct
13 Correct 107 ms 23976 KB Output is correct