oj.uz

Submission #718318

# Submission time Handle Problem Language Result Execution time Memory
718318 2023-04-03T20:51:37 Z lukameladze Synchronization (JOI13_synchronization) C++14
100 / 100
 219 ms 29684 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
// #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int t,n,k,q,a[N],x[N],y[N],in[N],tin,lv[N],par[N][20],out[N],ff;
int tree[N],lst[N],add[N],sz[N];
vector <int> v[N];
void dfs(int a, int p) {
	in[a] = ++tin;
	lv[a] = lv[p] + 1;
	par[a][0] = p;
	for (int i = 1; i <= 18; i++) {
		if (par[a][i - 1]) par[a][i] = par[par[a][i - 1]][i - 1];
	}
	for (int to : v[a]) {
		if (to == p) continue;
		dfs(to, a);
	}
	out[a] = tin;
}
void update(int idx, int val) {
	for (int i = idx; i < N; i+=i&(-i)) {
		tree[i] += val;
	}
}
int getans(int idx) {
	int pas = 0;
	for (int i = idx; i > 0; i-=i&(-i)) {
		pas += tree[i];
	}	
	return pas;
}
int get_root(int a) {
	
	int x = getans(in[a]);
	if (a == 1 || getans(in[a]) == getans(in[par[a][0]])) {
		return a;
	}
	int cur = a;
	for (int i = 18; i >= 0; i--) {
		if (!par[cur][i]) continue;
//		if (a == 6 && ff && i == 0) {
//			cout<<a<<" "<<cur<<" "<<par[cur][i]<<" "<<getans(in[par[cur][i]])<<" "<<x<<" "<<(lv[a] - lv[par[cur][i]] + 1)<<"\n";
//		}
		int pp = par[cur][i];
		if (x - getans(in[pp]) == (lv[a] - lv[pp])) cur = par[cur][i];
	}
	return cur;
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q>>k;
	for(int i = 1; i <= n - 1; i++) {
		cin>>x[i]>>y[i];
		v[x[i]].pb(y[i]);
		v[y[i]].pb(x[i]);
	}
	dfs(1, 0);
	for (int i = 1; i <= n - 1; i++) {
		if (lv[x[i]] > lv[y[i]]) swap(x[i], y[i]);
	}
	for (int i = 1; i <= n; i++) {
		sz[i] = 1; 
	}
	ff = 0;
	while (q--) {
		int idx;
		cin>>idx; 
		if (add[idx]) {  // remove edge
			int pr = sz[get_root(x[idx])];
			update(in[y[idx]], -1); 
			update(out[y[idx]] + 1, 1);
			lst[idx] = pr; sz[y[idx]] = pr;
			add[idx] = 0;
		} else { // add edge
			sz[get_root(x[idx])] = sz[get_root(y[idx])] + sz[get_root(x[idx])] - lst[idx];
			sz[get_root(y[idx])] = 0;
			update(in[y[idx]], 1);
			update(out[y[idx]] + 1, -1);
			add[idx] = 1;
		}
	}
	for (int i = 1; i <= k; i++) {
		int que;
		cin>>que; 
		cout<<sz[get_root(que)]<<"\n";
	}
}

Compilation message

synchronization.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main() {
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7356 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 14 ms 9092 KB Output is correct
8 Correct 14 ms 9104 KB Output is correct
9 Correct 13 ms 9044 KB Output is correct
10 Correct 190 ms 24248 KB Output is correct
11 Correct 215 ms 24196 KB Output is correct
12 Correct 156 ms 28888 KB Output is correct
13 Correct 85 ms 24240 KB Output is correct
14 Correct 111 ms 23244 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 24172 KB Output is correct
2 Correct 82 ms 26004 KB Output is correct
3 Correct 82 ms 27940 KB Output is correct
4 Correct 87 ms 27980 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7636 KB Output is correct
7 Correct 16 ms 9556 KB Output is correct
8 Correct 201 ms 29684 KB Output is correct
9 Correct 192 ms 29612 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 26832 KB Output is correct
2 Correct 135 ms 28940 KB Output is correct
3 Correct 137 ms 29164 KB Output is correct
4 Correct 136 ms 29240 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7468 KB Output is correct
3 Correct 5 ms 7420 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7580 KB Output is correct
6 Correct 17 ms 9044 KB Output is correct
7 Correct 219 ms 25128 KB Output is correct
8 Correct 197 ms 29668 KB Output is correct
9 Correct 98 ms 25312 KB Output is correct
10 Correct 143 ms 24588 KB Output is correct
11 Correct 114 ms 27424 KB Output is correct
12 Correct 109 ms 27320 KB Output is correct
13 Correct 135 ms 29100 KB Output is correct