Submission #1125893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125893		nuutsnoynton	Synchronization (JOI13_synchronization)	C++17	100 / 100	1800 ms	38916 KiB

synchronization

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 2e5 + 2;

ll etseg[N], huu[N], out[N], par[20][N], is_connected[N], in[N],val[N], depth[N], last_connected[N];
ll Sum[16 * N], Has[16 * N], n;
vector < ll > adj[N];

ll timer = 0;
void Go(ll cur, ll parent) {
	ll i;
	par[0][cur] = parent;
	for (i = 1; i <= 18; i++) par[i][cur] = par[i - 1][par[i - 1][cur]];
	is_connected[cur] = 0;
	in[cur] = ++timer;
//	par[cur] = parent;
	for ( ll child : adj[cur]) {
		if ( child == parent) continue;
		depth[child] = depth[cur] + 1;
		Go(child, cur);
		
	}
	out[cur] = timer;
	return ;
}



void PushDown(ll p, ll lo, ll hi) {
	ll mid = (lo +hi)/2;
	Has[2 * p] += (Has[p]);
	Has[2 * p + 1] += (Has[p]);
	Sum[2 * p] += (Has[p] * (mid - lo + 1));
	Sum[2 * p + 1] += (Has[p] * (hi - mid));
	Has[p] = 0;
}
void Update(ll p, ll lo, ll hi, ll l, ll r, ll val) {
	if ( lo > r || l > hi) return ;
	if ( l <= lo && hi <= r) {
		Has[p] += val;
		Sum[p] += (val * (hi - lo + 1));
		return ;
	}
	PushDown(p, lo, hi) ;
	ll mid = (lo + hi)/2;
	Update(2 * p, lo, mid, l, r, val);
	Update(2 * p + 1, mid + 1, hi, l, r, val);
	Sum[p] = Sum[2 * p] + Sum[2 * p + 1];
}
ll Find(ll p, ll lo, ll hi, ll x) {
	if (lo ==hi) return Sum[p];
	PushDown(p, lo, hi);
	ll mid = (lo + hi)/2;
	if ( x <=mid) return Find(2 * p, lo, mid, x);
	return Find(2 * p + 1, mid + 1, hi, x);
}


ll Check(ll x) {
	ll i, y, dist = 0, X, Y;
	for ( i = 18; i >= 0; i --) {
		y = par[i][x];
		X = in[x];
		Y = in[y];
		X = Find(1, 1, n, X);
		Y = Find(1, 1, n, Y);
		if ( depth[x] - depth[y] == X - Y) x = y;
	}
	return x;
}



int main() {
	ll m, r, x, y, s, i, j, ans, t, q;
	
	cin >> n >> m >> q;
	
	for (i = 1; i<= n; i ++) val[i] = 1;	
	for (i = 1; i < n; i++) {
		cin >> etseg[i] >> huu[i];
		adj[etseg[i]].push_back(huu[i]);
		adj[huu[i]].push_back(etseg[i]);
	}
	Go(1, 1);
	for (i = 1; i < n; i ++) {
		if ( depth[huu[i]] - 1 != depth[etseg[i]]) swap(etseg[i], huu[i]);
	}
	for (j = 1; j <= m; j ++) {
		cin >> i;	
		
		if ( is_connected[huu[i]]) {
			s = Check(huu[i]);
			val[huu[i]] = val[s];
			last_connected[huu[i]] = val[s];
			Update(1, 1, n, in[huu[i]], out[huu[i]], -1);
		}
		else {
			s = Check(etseg[i]);
			r = val[s] + val[huu[i]] - last_connected[huu[i]];
			val[s] = r;
			last_connected[huu[i]] = r;
			Update(1, 1, n, in[huu[i]], out[huu[i]], 1);
		}
		is_connected[huu[i]] ^= 1;
	//	for (i = 1; i <= n; i ++) {
	//		cout << val[i] << " ";
	//	}
	//	cout << endl;
	}
	for (i = 1; i <= q; i ++) {
		cin >> x;
		s = Check(x);
		cout << val[s] << endl;
	}
}

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