제출 #1318252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318252		aaaaaaaa	Synchronization (JOI13_synchronization)	C++20	0 / 100	8093 ms	28540 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()

/*
idea:

duita node unite hole
tader whole component answer increase hobe ans[u] + ans[v] - prev[edge]


functionss:

add(u, v)
remove(u, v)
root(u)





*/

const int mxN = 1e5 + 100;
const int mxB = 21;

vector<int> adj[mxN];
set<int> nadj[mxN];
int dp[mxN][mxB], depth[mxN], ans[mxN], xv[mxN], pans[mxN], st[mxN], en[mxN], seg[mxN * 4], tin = 1;

void dfs(int u = 1, int par = 0){
	st[u] = tin ++;
	dp[u][0] = par, depth[u] = depth[par] + 1;
	for(int j = 1; j < mxB; ++j) dp[u][j] = dp[dp[u][j - 1]][j - 1];
	for(auto it : adj[u]){
		if(it ^ par){
			dfs(it, u);
		}
	}
	en[u] = tin;
}

void upd(int idx, int v){
	idx += tin - 1;
	seg[idx] = v;
	while(idx > 1){
		idx >>= 1;
		seg[idx] = seg[idx << 1] + seg[idx << 1 | 1];
	}
}

int qry(int u){
	if(u == 0) return 0;
	int l = 1 + tin - 1, r = st[u] + tin - 1, sum = 0;
	while(l <= r){
		if(l & 1) sum += seg[l++];
		if(r & 1 ^ 1) sum += seg[r--];
		l >>= 1, r >>= 1;
	}
	return sum;
}

void update(int u, int val){
	xv[u] = val;
	upd(st[u], val);
	upd(en[u], -val);
}

int query(int u, int par){
	return qry(u) - qry(par);
}

int root(int u){
	/*int ans = u;
	for(int j = mxB - 1; j >= 0; --j){
		if(dp[u][j] != 0 && !(query(u, dp[u][j]) - xv[u])){
			u = dp[u][j];
		}
	}
	return u;	*/
	while((int) nadj[u].size()){
		u = *nadj[u].begin();
	}
	return u;
}

void unite(int u, int v){
	if(dp[u][0] == v) swap(u, v);
	u = root(u), v = root(v);
	int x = ans[u] + ans[v] - pans[v];
	ans[u] = x;
	update(v, 0);
	nadj[v].insert(u);
}

void remove(int u, int v){
	if(dp[u][0] == v) swap(u, v);
	ans[v] = pans[v] = ans[root(u)];
	update(v, 1);
	nadj[v].erase(u);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> active(m + 1, 0);
	vector<pair<int, int>> edges;
	for(int i = 0, u, v; i < n - 1; ++i){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.push_back({u, v});
	}dfs();
	for(int i = 1; i <= n; ++i) update(i, 1), ans[i] = 1;
	while(m--){
		int edge;
		cin >> edge; --edge;
		active[edge] ^= 1;
		if(active[edge]) unite(edges[edge].first, edges[edge].second);
		else remove(edges[edge].first, edges[edge].second);
	//	for(int i = 1; i <= n; ++i) cout << root(i) << " ";
	//	cout << "\n";
	}
	while(q--){
		int u;
		cin >> u;
		cout << ans[root(u)] << "\n";
	}
	return 0;
}

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