Submission #1255953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255953		kamrad	Synchronization (JOI13_synchronization)	C++20	100 / 100	143 ms	15292 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("Ofast,unroll-loops")
//pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pi3 = pair<pii, int>;

#define IOS               ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F                 first
#define S                 second
#define sz(x)             x.size()
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define cl                clear
#define minr(a, b)        a = min(a, b);
#define maxr(a, b)        a = max(a, b);
#define shit              cout << "shit\n" << flush;
#define tl                while(1&1) continue;
#define FOR(i, st, nd)    for(int i = st; i <= n; i++)
#define rand(l, r)        uniform_int_distribution<int64_t>(l,r)(rng)
random_device device;     default_random_engine rng(device());

const int Mod    = 1e9 + 7; //998244353;
const int LG     = 64;
const int SQ     = 500;
const int Inf    = 2e9 + 10;
const int maxN   = 1e5 + 10;

int n, m, q;
int tim = 1;

int h[maxN];
int st[maxN];
int ft[maxN];
int cur[maxN];
int lst[maxN];
int stNode[maxN];

bool mark[maxN];
bool active[maxN];

vector <int> neighb[maxN];
vector <pii> edges;

struct RootSegTree {
	struct Node {
		int MxR;
		Node() {
			MxR = 0;
		}
	} t[maxN<<2];

	void initialize(int id, int L, int R) {
		if(L+1 == R) {
			t[id].MxR = ft[stNode[L]];
			return;
		}

		int mid = (L+R)>>1;
		initialize(2*id+0, L, mid);
		initialize(2*id+1, mid, R);
		t[id].MxR = max(t[2*id+0].MxR, t[2*id+1].MxR);
	}

	void update(int id, int L, int R, int idx, int val) {
		if(L+1 == R) {
			t[id].MxR = val;
			return ;
		}

		int mid = (L+R)>>1;
		if(idx < mid)
			update(2*id+0, L, mid, idx, val);
		else
			update(2*id+1, mid, R, idx, val);
		t[id].MxR = max(t[2*id+0].MxR, t[2*id+1].MxR);
	}

	int search(int id, int L, int R, int val) {
		if(L+1 == R)
			return L;

		int mid = (L+R)>>1;
		if(t[2*id+1].MxR >= val)
			return search(2*id+1, mid, R, val);
		return search(2*id+0, L, mid, val);
	}

	int GetRoot(int id, int L, int R, int l, int r, int val) {
		if(t[id].MxR < val)
			return -1;

		if(L == l and R == r)
			return search(id, L, R, val);

		int mid = (L+R)>>1;
		if(r <= mid)
			return GetRoot(2*id+0, L, mid, l, min(mid, r), val);

		int tmp = GetRoot(2*id+1, mid, R, max(l, mid), r, val);
		if(tmp >= 1)
			return tmp;
		return GetRoot(2*id+0, L, mid, l, min(mid, r), val);
	}

} rst;

void dfs(int u) {
	st[u] = tim;
	stNode[tim] = u;
	tim++;
	mark[u] = true;
	for(auto v : neighb[u]) {
		if(!mark[v]) {
			dfs(v);
		}
	}
	ft[u] = tim-1;
}

int main() {
	IOS;

	int n, m, q;
	cin >> n >> m >> q;

	for(int i = 1; i <= n-1; i++) {
		int u, v;
		cin >> u >> v;
		neighb[u].pb(v);
		neighb[v].pb(u);
		edges.pb({u, v});
	}

	dfs(1);
	rst.initialize(1, 1, n+1);
	
	for(int i = 1; i <= n; i++)
		cur[i] = 1;

	while(m--) {
		int idx;
		cin >> idx;

		int u = edges[idx-1].F;
		int v = edges[idx-1].S;

		if(st[u] > st[v])
			swap(u, v);

		if(active[idx]) {
			active[idx] = false;
			int root = rst.GetRoot(1, 1, n+1, 1, st[v]+1, st[v]);
			rst.update(1, 1, n+1, st[v], ft[v]);
			cur[v] = cur[stNode[root]];
			lst[v] = cur[v];
		}
		else {
			active[idx] = true;
			int root = rst.GetRoot(1, 1, n+1, 1, st[u]+1, st[u]);
			rst.update(1, 1, n+1, st[v], 0);
			cur[stNode[root]] += (cur[v]-lst[v]);
		}
	}

	while(q--) {
		int u;
		cin >> u;

		int root = rst.GetRoot(1, 1, n+1, 1, st[u]+1, st[u]);
		cout << cur[stNode[root]] << "\n";
	}
}

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