oj.uz

답안 #713711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713711 2023-03-22T21:10:09 Z study 동기화 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 457 ms 27196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2772 KB Output isn't correct
2 Halted 0 ms 0 KB -