oj.uz

Submission #714910

# Submission time Handle Problem Language Result Execution time Memory
714910 2023-03-25T12:36:53 Z study Synchronization (JOI13_synchronization) C++17
100 / 100
 752 ms 28264 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],sync[N],queries[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);
	}
	for (int i=0; i<q; ++i){
		cin >> queries[i];
		--queries[i];
	}
	int root = 0;
	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] = 0;
	}
	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);
			u = getRoot(u);
			sync[v] = res[v] = res[u];
		}
		else{
			modify(tin[v],-1);
			modify(tout[v],1);
			u = getRoot(u);
			res[v] = res[u] = sync[v] = res[u]+res[v]-sync[v];
		}	
		status[v] = 1-status[v];
	}
	for (int i=0; i<q; ++i){
		cout << res[getRoot(queries[i])] << '\n';
	}
	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 2772 KB Output is correct
6 Correct 4 ms 2940 KB Output is correct
7 Correct 31 ms 4744 KB Output is correct
8 Correct 26 ms 4720 KB Output is correct
9 Correct 27 ms 4724 KB Output is correct
10 Correct 555 ms 20904 KB Output is correct
11 Correct 599 ms 20940 KB Output is correct
12 Correct 620 ms 27040 KB Output is correct
13 Correct 116 ms 20652 KB Output is correct
14 Correct 336 ms 20388 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 21728 KB Output is correct
2 Correct 87 ms 21652 KB Output is correct
3 Correct 142 ms 24704 KB Output is correct
4 Correct 142 ms 26380 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2804 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 4 ms 3068 KB Output is correct
7 Correct 35 ms 5440 KB Output is correct
8 Correct 666 ms 28208 KB Output is correct
9 Correct 749 ms 28196 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 25248 KB Output is correct
2 Correct 232 ms 27904 KB Output is correct
3 Correct 248 ms 28028 KB Output is correct
4 Correct 247 ms 28036 KB Output is correct

Subtask #5
40.0 / 40.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 2772 KB Output is correct
5 Correct 4 ms 3028 KB Output is correct
6 Correct 39 ms 4764 KB Output is correct
7 Correct 752 ms 22024 KB Output is correct
8 Correct 725 ms 28264 KB Output is correct
9 Correct 149 ms 22244 KB Output is correct
10 Correct 355 ms 21888 KB Output is correct
11 Correct 114 ms 25356 KB Output is correct
12 Correct 118 ms 25352 KB Output is correct
13 Correct 254 ms 28104 KB Output is correct