Submission #1138003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138003		SmuggingSpun	Synchronization (JOI13_synchronization)	C++20	100 / 100	185 ms	22572 KiB

synchronization

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
const int lim = 1e5 + 5;
const int INF = 1e9;
int n, m, q, euler = 0, low[lim], tail[lim], h[lim], ans[lim], pre_edge_ans[lim], bit[lim], up[lim][17];
pair<int, int>edge[lim];
vector<int>g[lim];
bitset<lim>state;
void update(int p, int x){
	for(; p <= n; p += p & -p){
		bit[p] += x;
	}
}
void update(int l, int r, int x){
	update(l, x);
	update(r + 1, -x);
}
int get(int p){
	int ans = 0;
	for(; p > 0; p -= p & -p){
		ans += bit[p];
	}
	return ans;
}
void dfs(int s){
	low[s] = ++euler;
	for(int& d : g[s]){
		if(d != up[s][0]){
			h[d] = h[up[d][0] = s] + 1;
			for(int i = 1; i < 17; i++){
				up[d][i] = up[up[d][i - 1]][i - 1];
			}
			dfs(d);
		}
	}
	tail[s] = euler;
}
int get_represent(int u){
	for(int i = 16; i > -1; i--){
		if(up[u][i] != 0 && get(low[u]) - get(low[up[u][i]]) == (1 << i)){
			u = up[u][i];
		}
	}	
	return u;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		cin >> edge[i].first >> edge[i].second;
		g[edge[i].first].emplace_back(edge[i].second);
		g[edge[i].second].emplace_back(edge[i].first);
	}
	memset(up, h[1] = 0, sizeof(up));
	dfs(1);
	for(int i = 1; i < n; i++){
		if(h[edge[i].first] > h[edge[i].second]){
			swap(edge[i].first, edge[i].second);
		}
	}
	state.reset();
	memset(bit, 0, sizeof(bit));
	memset(pre_edge_ans, 0, sizeof(pre_edge_ans));
	fill(ans + 1, ans + n + 1, 1);
	for(int _ = 0; _ < m; _++){
		int x;
		cin >> x;
		state.flip(x);
		auto& [u, v] = edge[x];
		if(state.test(x)){
			ans[u] = (ans[get_represent(u)] += ans[v] - pre_edge_ans[x]);
			update(low[v], tail[v], 1);
		}
		else{
			pre_edge_ans[x] = ans[v] = ans[u] = ans[get_represent(u)];
			update(low[v], tail[v], -1);
		}
	}
	for(int _ = 0; _ < q; _++){
		int x;
		cin >> x;
		cout << ans[get_represent(x)] << "\n";
	}
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:50:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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