oj.uz

Submission #1098806

# Submission time Handle Problem Language Result Execution time Memory
1098806 2024-10-10T03:09:31 Z Alihan_8 Synchronization (JOI13_synchronization) C++17
20 / 100
 8000 ms 13652 KB 
#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);
	};
	
	while ( q-- ){
		int x; cin >> x;
		
		cout << calc(x - 1) << '\n';
	}
	
	cout << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 452 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 1372 KB Output is correct
8 Incorrect 4 ms 1356 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12500 KB Output is correct
2 Correct 28 ms 11216 KB Output is correct
3 Correct 26 ms 13652 KB Output is correct
4 Correct 26 ms 13112 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8050 ms 10436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -