Submission #718300

#	Time	Username	Problem	Language	Result	Execution time	Memory
718300		lukameladze	Synchronization (JOI13_synchronization)	C++14	0 / 100	402 ms	29560 KiB

synchronization

# 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 (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40