Submission #1098807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098807		Alihan_8	Synchronization (JOI13_synchronization)	C++17	20 / 100	33 ms	13376 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ar array

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, q; cin >> n >> m >> q;
	
	vector <int> X(n - 1), Y(n - 1);
	
	for ( int i = 0; i < n - 1; i++ ){
		cin >> X[i] >> Y[i];
		
		--X[i], --Y[i];
	}
	
	vector <int> state(n - 1), R(n - 1, -1), L(n - 1, m + 1);
	
	for ( int i = 0; i < m; i++ ){
		int x; cin >> x;
		
		--x;
		
		if ( L[x] == m + 1 ) L[x] = i;
		 
		R[x] = i;
		state[x] ^= 1;
	}
	
	for ( int i = 0; i < n - 1; i++ ){
		if ( state[i] > 0 ) R[i] = m;
	}
	
	auto calc = [&](int rt){
		vector <vector<ar<int,2>>> adj(n);
		
		for ( int i = 0; i < n - 1; i++ ){
			adj[X[i]].pb({Y[i], i});
			adj[Y[i]].pb({X[i], i});
		}
		
		auto dfs = [&](auto dfs, int u, int p, int r) -> int{
			int ret = 1;
			
			for ( auto &[v, j]: adj[u] ){
				if ( v != p ){
					if ( r > L[j] ){
						ret += dfs(dfs, v, u, min(r, R[j]));
					}
				} 
			}
			
			return ret;
		};
		
		return dfs(dfs, rt, -1, m);
	};
	
	assert(q == 1);
	
	while ( q-- ){
		int x; cin >> x;
		
		cout << calc(x - 1) << '\n';
	}
	
	cout << '\n';
}

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