oj.uz

Submission #972883

# Submission time Handle Problem Language Result Execution time Memory
972883 2024-05-01T09:29:49 Z dio_2 Synchronization (JOI13_synchronization) C++17
40 / 100
 8000 ms 16916 KB 
#include<bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, q;
	cin >> n >> m >> q;
	
	vector<vector<int>> g(n + 1);
	vector<pair<int, int>> kraw(n);
	vector<int> state_kraw(n); // na poczatky wszytko jest off.
	
	for(int i = 0;i < n - 1;i++){
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
		kraw[i + 1] = make_pair(a, b);
	}
	
	vector<int> dep(n + 1), tin(n + 1), tout(n + 1);
	vector<int> parent(n + 1), parent_kraw(n + 1);
	vector<int> passed_cnt(n + 1); // ile przeszlo od danej krawedzi
	vector<int> info(n + 1, 1); // ile informacij ma dane korzenie ( czyli leader DSU )
	int T = 1;
	auto dfs1 = [&](auto &&dfs1, int u, int p)->void{
		tin[u] = T++;
		for(int v : g[u]) if(v != p){
			parent[v] = u;
			dep[v] = dep[u] + 1;
			dfs1(dfs1, v, u);
		}
		tout[u] = T++;
	}; dfs1(dfs1, 1, 0);
	
	for(int i = 1;i <= n - 1;i++){
		auto [a, b] = kraw[i];
		if(dep[a] > dep[b]) swap(a, b);
		parent_kraw[b] = i;
	}
	
	while(m--){
		int e;
		cin >> e;
		
		auto [a, b] = kraw[e];
		if(dep[a] > dep[b]) swap(a, b);
		// a na gorze
		
		if(!state_kraw[e]){ // polacz 
			// b jest korzeniem dolnego poddrzewa
			// dla a nie wiemy kim jest leaderem treba isc do gory do poki mozna
			while(parent[a] and state_kraw[ parent_kraw[a] ] ) a = parent[a]; // this is the bottle-neck.
			
			int przejdzie = info[b] - passed_cnt[e];
			info[a] += przejdzie;
			passed_cnt[e] += przejdzie;
		} else { // rozlacz
			while(parent[a] and state_kraw[ parent_kraw[a] ] ) a = parent[a];
			passed_cnt[e] = info[a];
			info[b] = info[a];
		}
		
		state_kraw[e] ^= 1;
	}
	
	for(int i = 0;i < q;i++){
		int a;
		cin >> a;
		while(parent[a] and state_kraw[ parent_kraw[a] ] ) a = parent[a];
		cout << info[a] << '\n';                              
	}
	
	return 0;	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 1372 KB Output is correct
8 Correct 4 ms 1372 KB Output is correct
9 Correct 7 ms 1372 KB Output is correct
10 Correct 56 ms 12132 KB Output is correct
11 Correct 51 ms 12124 KB Output is correct
12 Correct 45 ms 16088 KB Output is correct
13 Correct 33 ms 12044 KB Output is correct
14 Correct 40 ms 11476 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
10.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 344 KB Output is correct
4 Correct 0 ms 544 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 5 ms 2056 KB Output is correct
8 Correct 64 ms 16776 KB Output is correct
9 Correct 55 ms 16720 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13908 KB Output is correct
2 Correct 5665 ms 16420 KB Output is correct
3 Correct 5786 ms 16524 KB Output is correct
4 Correct 5781 ms 16908 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 6 ms 1624 KB Output is correct
7 Correct 75 ms 13016 KB Output is correct
8 Correct 61 ms 16916 KB Output is correct
9 Correct 46 ms 13128 KB Output is correct
10 Correct 70 ms 12884 KB Output is correct
11 Execution timed out 8069 ms 14088 KB Time limit exceeded
12 Halted 0 ms 0 KB -