Submission #1318179

#TimeUsernameProblemLanguageResultExecution timeMemory
1318179aaaaaaaaSynchronization (JOI13_synchronization)C++20
0 / 100
3 ms2360 KiB
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()

const int mxN = 10005;

vector<pair<int, int>> adj[mxN];
set<int> en_time[mxN], st_time[mxN];
int ans = 0;

void dfs(int u = 1, int par = 0, int tim = mxN){
	ans += 1;
	for(auto [v, t] : adj[u]){
		if(v == par) continue;
		if((int) st_time[t].size() == 0) continue;
		if((int) *st_time[t].begin() > tim) continue;
		auto lb = en_time[t].lower_bound(tim);
		if(lb == en_time[t].end()) --lb;
		dfs(v, u, min(*lb, tim));
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> on(n + 5, 0);
	for(int i = 0, u, v; i < n - 1; ++i){
		cin >> u >> v;
		adj[u].push_back({v, i + 1});
		adj[v].push_back({u, i + 1});
	}
	for(int i = 0, x; i < m; ++i){
		cin >> x;
		on[x] ^= 1;
		if(on[x]){
			st_time[x].insert(i);
		}else{
			en_time[x].insert(i);
		}
	}
	for(int i = 0; i < n; ++i){
		if((int) en_time[i + 1].size() == 0){
			en_time[i + 1].insert(mxN);
		}
	}
	int x;
	cin >> x;
	dfs(x);
	cout << ans << "\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...