Submission #1137025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137025		shiro	Synchronization (JOI13_synchronization)	C++20	100 / 100	278 ms	24060 KiB

synchronization

#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <string>
#include <set>
#include <functional>
#include <complex>
#include <queue>
#include <random>
#include <chrono>
#include <unordered_map>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,tune=native")
typedef long double ld;
using ll = int;
using ld = long double;
using ull = unsigned long long;
using pp = std::pair<ll, ll>;
using mll = std::map<ll, ll>;
using cd = std::complex<double>;
using unm = std::unordered_map<ll, ll>;
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define yes cout << "YES" << '\n'
#define no cout << "NO" << '\n'
#define DDD ll gcd(ll a, ll b) { while (b) b ^= a ^= b ^= a %= b; return a; }
#define RRR mt19937 rand_(chrono::steady_clock::now().time_since_epoch().count()); ll randll() { return uniform_int_distribution<ll>()(rand_); }
using namespace std;
ll n, m, q;
vector<ll> g[100005];
pp uwu[100005];
ll  Z[100005][20], depth[100005], 
	t = 1, tin[100005], tout[100005], fin[200005], used[100005], debt[100005], cnt[100005];


void ZZZ(ll node = 1, ll pr = 1, ll dep = 1) {
	cnt[node] = 1;
	tin[node] = t; t++;
	depth[node] = dep;
	Z[node][0] = pr;
	for (ll st = 1; st < 20; st++) {
		Z[node][st] = Z[Z[node][st - 1]][st - 1];
	}
	for (ll to : g[node]) {
		if (to != pr) {
			ZZZ(to, node, dep + 1);
		}
	}
	tout[node] = t; t++;
}

void ADD(ll pos, ll val) {
	for (; pos <= 200002; pos += pos & -pos) 
		fin[pos] += val;
}
ll GET(ll pos) {
	ll res = 0;
	for (; pos > 0; pos -= pos & -pos)
		res += fin[pos];
	return res;
}
void FIN() {
	for (ll node = 2; node <= n; node++) {
		ADD(tin[node], 1);
		ADD(tout[node], -1);
	}
}

ll boss(ll node) {
	for (ll st = 19; st >= 0; st--) {
		if (GET(tin[node]) == GET(tin[Z[node][st]])) {
			node = Z[node][st];
		}
	}
	return node;
}

void solve(ll a) {
	used[a] ^= 1;
	ll v = uwu[a].first;
	ll u = uwu[a].second;
	if (depth[v] > depth[u]) swap(v, u);
	if (used[a]) { // connect
		v = boss(v);
		cnt[v] = cnt[v] + cnt[u] - debt[u];
		ADD(tin[u], -1);
		ADD(tout[u], 1);
	}
	else {         // split
		v = boss(v);
		cnt[u] = debt[u] = cnt[v];
		ADD(tin[u], 1);
		ADD(tout[u], -1);
	}
}

int main() {
	speed;
	cin >> n >> m >> q;
	for (ll i = 1; i < n; i++) {
		cin >> uwu[i].first >> uwu[i].second;
		g[uwu[i].first].push_back(uwu[i].second);
		g[uwu[i].second].push_back(uwu[i].first);
	}
	ZZZ();
	FIN();
	while (m--) {
		ll a;
		cin >> a;
		solve(a);
	}
	while (q--) {
		ll node;
		cin >> node;
		cout << cnt[boss(node)] << endl;
	}
}

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