oj.uz

Submission #409112

# Submission time Handle Problem Language Result Execution time Memory
409112 2021-05-20T08:19:57 Z vuhoanggiap Synchronization (JOI13_synchronization) C++17
100 / 100
 368 ms 25444 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int maxN = 1e5 + 5, maxM = 2e5 + 5;  
int n, m, q; 
vector<int> adj[maxN]; 

int A[maxM], B[maxM]; 
bool state[maxM]; 

int euler; 
int s[maxN], e[maxN]; 
int jump[maxN][22]; 

void dfs(int u, int p) {
	s[u] = ++euler; 
	jump[u][0] = p; 
	for(int i = 1; i < 20; i++) 
		jump[u][i] = jump[jump[u][i - 1]][i - 1]; 
	for(auto v : adj[u])
		if(v != p)
			dfs(v, u); 
	e[u] = euler; 
}

int fen[maxN]; 
void update(int i, int val) { while(i <= n + 1) fen[i] += val, i += (i & (-i)); }
int query(int i) { int ret = 0; while(i) ret += fen[i], i -= (i & (-i)); return ret; }

int ancestor(int u) {
	int oldu = u; 
	for(int i = 19; i >= 0; i--) 
		if(query(s[oldu]) == query(s[jump[u][i]]))
			u = jump[u][i]; 
	return u; 
}

int distinct[maxN], distinctUp[maxN]; 
int ans[maxN]; 

signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q; 
	for(int i = 1; i < n; i++) {
		cin >> A[i] >> B[i]; 
		adj[A[i]].pb(B[i]); 
		adj[B[i]].pb(A[i]); 
	} 
	dfs(1, 1);
	for(int i = 1; i <= n; i++) {
		distinct[i] = 1; 
		update(s[i], 1); 
		update(e[i] + 1, -1); 
	}
	for(int i = 1; i < n; i++) 
		if(jump[A[i]][0] == B[i])
			swap(A[i], B[i]); 
	for(int i = 1; i <= m; i++) {
		int id; cin >> id; 
		if(!state[id]) {
			int u = ancestor(A[id]); 
			distinct[u] += distinct[B[id]] - distinctUp[B[id]]; 
			update(s[B[id]], -1); 
			update(e[B[id]] + 1, 1); 
		}
		else {
			int u = ancestor(A[id]); 
			distinct[B[id]] = distinctUp[B[id]] = distinct[u]; 
			update(s[B[id]], 1); 
			update(e[B[id]] + 1, -1); 
		}
		state[id] ^= 1; 
	}
	for(int i = 1; i <= n; i++) {
		ans[i] = distinct[ancestor(i)]; 
 	}
 	for(int i = 1; i <= q; i++) {
 		int u; cin >> u; 
 		cout << ans[u] << '\n'; 
 	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2664 KB Output is correct
6 Correct 5 ms 2764 KB Output is correct
7 Correct 27 ms 4368 KB Output is correct
8 Correct 21 ms 4372 KB Output is correct
9 Correct 27 ms 4356 KB Output is correct
10 Correct 282 ms 20028 KB Output is correct
11 Correct 282 ms 19956 KB Output is correct
12 Correct 301 ms 24652 KB Output is correct
13 Correct 158 ms 19856 KB Output is correct
14 Correct 215 ms 19116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 21940 KB Output is correct
2 Correct 151 ms 21600 KB Output is correct
3 Correct 177 ms 23776 KB Output is correct
4 Correct 176 ms 23708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2664 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 27 ms 4812 KB Output is correct
8 Correct 336 ms 25444 KB Output is correct
9 Correct 321 ms 25404 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 25376 KB Output is correct
2 Correct 191 ms 24776 KB Output is correct
3 Correct 212 ms 24892 KB Output is correct
4 Correct 193 ms 24820 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 4 ms 2804 KB Output is correct
6 Correct 29 ms 4424 KB Output is correct
7 Correct 300 ms 20824 KB Output is correct
8 Correct 325 ms 25424 KB Output is correct
9 Correct 178 ms 21104 KB Output is correct
10 Correct 203 ms 20292 KB Output is correct
11 Correct 174 ms 23024 KB Output is correct
12 Correct 174 ms 23164 KB Output is correct
13 Correct 192 ms 25028 KB Output is correct