Submission #973466

#	Time	Username	Problem	Language	Result	Execution time	Memory
973466		beaboss	Synchronization (JOI13_synchronization)	C++14	100 / 100	365 ms	25340 KiB

synchronization

// Source: https://oj.uz/problem/view/JOI13_synchronization
//  

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

#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back

typedef vector<int> vi;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int B = 20;

int bit[N];
void add(int ind, int val) {
	for (; ind < N; ind += (ind & -ind)) {
		bit[ind] += val;
	}
}
int query(int ind) {
	int res = 0;
	for (; ind > 0; ind -= (ind & -ind)) {
		res += bit[ind];
	}
	return res;
}


vi adj[N];
vector<pii> con;
int lift[N][B], tin[N], tout[N], last[N], info[N], d[N], active[N];
int timer = 1;
void dfs(int cur, int par = 0) {
	lift[cur][0]=par;
	d[cur]=d[par]+1;
	tin[cur]=timer++;
	for (auto val: adj[cur]) {
		if (val != par) dfs(val, cur);
	}
	tout[cur]=timer;
}

int get(int cur) {
	int path = query(tin[cur]);
	for (int i = B - 1; i >= 0; i--) {
		if (lift[cur][i] != 0 && query(tin[lift[cur][i]]) == path) cur=lift[cur][i];
	}
	return cur;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m, q;
	cin >> n >> m >> q;
	con.pb({0, 0});
	FOR(i, 0, n-1) {

		int a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
		con.pb({a, b});
	}

	dfs(1);
	FOR(j, 1, B) FOR(i, 1, n + 1) lift[i][j] = lift[lift[i][j-1]][j-1];

	FOR(i, 1, n + 1) {
		// cout << i << endl;
		add(tin[i], 1);
		add(tout[i], -1);
		info[i]=1;
	}
	FOR(_, 0, m) {
		int sw;cin >> sw;

		int a = con[sw].first;
		int b = con[sw].second;
		if (d[a] < d[b]) swap(a, b);
		// cout << a << b << endl;
		if (active[sw]) {
			info[a] = info[get(b)];
			last[sw] = info[a];
			add(tin[a], 1);
			add(tout[a], -1);
		} else {
			info[get(b)] += info[a] - last[sw];
			add(tin[a], -1);
			add(tout[a], 1);
		}

		// cout << query(1) << query(2) << endl;
		// FOR(i, 1, n +1 ) cout << info[get(i)] << ' ';
		// cout << endl;
		active[sw] = !active[sw]; 

	}
	FOR(_, 0, q) {
		int node;
		cin >> node;
		cout << info[get(node)] << endl;
	}
}

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