Submission #718318

#	Time	Username	Problem	Language	Result	Execution time	Memory
718318		lukameladze	Synchronization (JOI13_synchronization)	C++14	100 / 100	219 ms	29684 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],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 (stderr)

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

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