oj.uz

Submission #713711

# Submission time Handle Problem Language Result Execution time Memory
713711 2023-03-22T21:10:09 Z study Synchronization (JOI13_synchronization) C++17
30 / 100
 457 ms 27196 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

vector<int> adj[N];
int tin[N],tout[N],segt[2*N],pere[20][N],res[N],status[N],depth[N];
int t = 0;

void dfs(int node, int p, int d){
	tin[node] = t;
	depth[node] = d;
	t++;
	for (int i:adj[node]){
		if (i != p){
			pere[0][i] = node;
			dfs(i,node,d+1);
		}
	}
	tout[node] = t;
}

void modify(int node, int val){
	node += N;
	segt[node] += val;
	node >>= 1;
	while (node){
		segt[node] = segt[2*node]+segt[2*node+1];
		node >>= 1;
	}
}

int query(int deb, int fin){
	deb += N;
	fin += N;
	int ans = 0;
	while (deb <= fin){
		if (deb&1){
			ans += segt[deb];
			deb++;
		}
		if (fin%2 == 0){
			ans += segt[fin];
			fin--;
		}
		deb >>= 1;
		fin >>= 1;
	}
	return ans;
}

int getRoot(int node){
	for (int i=19; i>=0; --i){
		if (query(tin[pere[i][node]]+1,tin[node]) == 0){
			node = pere[i][node];
		}
	}
	return node;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,q;
	cin >> n >> m >> q;
	vector<pair<int,int>> edges;
	for (int i=1; i<n; ++i){
		int u,v;
		cin >> u >> v;
		u--; v--;
		edges.emplace_back(u,v);
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	vector<int> event;
	for (int i=0; i<m; ++i){
		int a;
		cin >> a;
		a--;
		event.emplace_back(a);
	}
	int root = 0;
	for (int i=0; i<q; ++i){
		cin >> root;
	}
	root--;
	pere[0][root] = root;
	dfs(root,-1,0);
	for (int i=0; i<n; ++i){
		modify(tin[i],1);
		modify(tout[i],-1);
		res[i] = 1;
		status[i] = 1;
	}
	for (int i=1; i<20; ++i){
		for (int node=0; node<n; ++node){
			pere[i][node] = pere[i-1][pere[i-1][node]];
		}
	}
	for (int i=0; i<m; ++i){
		int u = edges[event[i]].first, v = edges[event[i]].second;
		if (depth[u] > depth[v]) swap(u,v);
		if (status[v] == 1){
			modify(tin[v],-1);
			modify(tout[v],1);
		}
		else{
			modify(tin[v],1);
			modify(tout[v],-1);
		}	
		status[v] = 1-status[v];
		if (status[v] == 0){
			res[getRoot(u)] += res[v];
			res[v] = 0;
		}
	}
	cout << res[getRoot(root)];
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2800 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 19 ms 4692 KB Output is correct
8 Correct 21 ms 4608 KB Output is correct
9 Correct 20 ms 4692 KB Output is correct
10 Correct 434 ms 20476 KB Output is correct
11 Correct 436 ms 20472 KB Output is correct
12 Correct 413 ms 23968 KB Output is correct
13 Correct 124 ms 20288 KB Output is correct
14 Correct 271 ms 19948 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 23404 KB Output is correct
2 Correct 92 ms 21756 KB Output is correct
3 Correct 125 ms 25448 KB Output is correct
4 Correct 111 ms 24632 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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