oj.uz

Submission #714906

# Submission time Handle Problem Language Result Execution time Memory
714906 2023-03-25T12:26:46 Z study Synchronization (JOI13_synchronization) C++17
0 / 100
 494 ms 26408 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);
			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
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 Incorrect 2 ms 2732 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 21776 KB Output is correct
2 Correct 85 ms 23656 KB Output is correct
3 Incorrect 148 ms 26408 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 494 ms 25252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
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 Incorrect 2 ms 2772 KB Output isn't correct
4 Halted 0 ms 0 KB -