oj.uz

Submission #718300

# Submission time Handle Problem Language Result Execution time Memory
718300 2023-04-03T20:01:16 Z lukameladze Synchronization (JOI13_synchronization) C++14
0 / 100
 402 ms 29560 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];
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 (getans(in[a]) == 0) {
		return a;
	}
	int cur = a;
	for (int i = 18; i >= 0; i--) {
		if (!par[cur][i]) continue;
		if (getans(in[par[cur][i]]) == x - (lv[a] - lv[par[cur][i]] + 1)) cur = par[cur][i];
	}
	return par[cur][0];
}
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; 
	}
	while (q--) {
		int idx;
		cin>>idx; 
		if (add[idx]) { 
			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 {
			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:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main() {
      | ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Incorrect 4 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 26132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 402 ms 29560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Incorrect 5 ms 7376 KB Output isn't correct
3 Halted 0 ms 0 KB -