oj.uz

Submission #66160

# Submission time Handle Problem Language Result Execution time Memory
66160 2018-08-09T22:24:03 Z zadrga Synchronization (JOI13_synchronization) C++14
100 / 100
 388 ms 18212 KB 
/*
Idea:
- All nodes within the same connected component have equal size
- When we add a connection, we add difference in size of currect vertex to the lowest reachable ancestor
- When we remove a connection, size of current vertex is the same as size of the lowest reachable ancestor (as stated in the first line)
- This can be easily maintained using segment tree
*/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 100111

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

vector<int> adj[maxn];
pii edge[maxn];
int in[maxn], out[maxn], pos[maxn], dep[maxn], last[maxn], sz[maxn];
int seg[4 * maxn];
bool state[maxn];
int cnt;

void DFS(int x, int p){
	in[x] = ++cnt;
	pos[cnt] = x;
	for(int v : adj[x]){
		if(v == p)
			continue;

		dep[v] = dep[x] + 1;
		DFS(v, x);
	}
	out[x] = cnt;
}

void build(int x, int l, int d){
	if(l > d)
		return;

	if(l == d){
		seg[x] = out[pos[l]];
		return;
	}

	int mid = (l + d) / 2;
	build(2 * x, l, mid);
	build(2 * x + 1, mid + 1, d);
	seg[x] = max(seg[2 * x], seg[2 * x + 1]);
}

void update(int x, int l, int d, int i, int val){
	if(l > d || i < l || i > d)
		return;

	if(l == d && l == i){
		seg[x] = val;
		return;
	}

	int mid = (l + d) / 2;
	update(2 * x, l, mid, i, val);
	update(2 * x + 1, mid + 1, d, i, val);
	seg[x] = max(seg[2 * x], seg[2 * x + 1]);
}

int findAncestor(int x, int l, int d, int i, int j){
	if(l > d || l > i || seg[x] < j)
		return -1;

	if(l == d)
		return pos[l];

	int mid = (l + d) / 2;
	int ret = findAncestor(2 * x + 1, mid + 1, d, i, j);
	if(ret == -1)
		ret = findAncestor(2 * x, l, mid, i, j);

	return ret;
}

int main(){
	int n, m, q;
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= n - 1; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].pb(b);
		adj[b].pb(a);
		edge[i] = mp(a, b);
	}

	DFS(1, -1);

	for(int i = 1; i <= n; i++){
		last[i] = 0;
		sz[i] = 1;
	}

	for(int i = 1; i <= n - 1; i++){
		state[i] = 0;
		if(dep[edge[i].fi] > dep[edge[i].se])
			swap(edge[i].fi, edge[i].se);		
	}

	build(1, 1, n);

	while(m--){
		int ind;
		scanf("%d", &ind);

		int from = edge[ind].fi;
		int to = edge[ind].se;
		int anc = findAncestor(1, 1, n, in[from], out[from]);

		if(!state[ind]){
			sz[anc] += sz[to] - last[to];
			update(1, 1, n, in[to], 0);
		}
		else{
			sz[to] = last[to] = sz[anc];
			update(1, 1, n, in[to], out[to]);
		}

		state[ind] ^= 1;
	}

	while(q--){
		int x;
		scanf("%d", &x);
		int anc = findAncestor(1, 1, n, in[x], out[x]);
		printf("%d\n", sz[anc]);
	}

	return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
synchronization.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &ind);
   ~~~~~^~~~~~~~~~~~
synchronization.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 4 ms 2876 KB Output is correct
4 Correct 5 ms 2876 KB Output is correct
5 Correct 4 ms 3036 KB Output is correct
6 Correct 6 ms 3036 KB Output is correct
7 Correct 21 ms 3928 KB Output is correct
8 Correct 21 ms 4120 KB Output is correct
9 Correct 23 ms 4312 KB Output is correct
10 Correct 286 ms 12972 KB Output is correct
11 Correct 288 ms 12972 KB Output is correct
12 Correct 244 ms 17400 KB Output is correct
13 Correct 271 ms 17400 KB Output is correct
14 Correct 207 ms 17400 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 17400 KB Output is correct
2 Correct 134 ms 17400 KB Output is correct
3 Correct 102 ms 17464 KB Output is correct
4 Correct 111 ms 17552 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17552 KB Output is correct
2 Correct 4 ms 17552 KB Output is correct
3 Correct 5 ms 17552 KB Output is correct
4 Correct 4 ms 17552 KB Output is correct
5 Correct 5 ms 17552 KB Output is correct
6 Correct 7 ms 17552 KB Output is correct
7 Correct 25 ms 17552 KB Output is correct
8 Correct 307 ms 17680 KB Output is correct
9 Correct 303 ms 17824 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 17824 KB Output is correct
2 Correct 168 ms 18096 KB Output is correct
3 Correct 160 ms 18212 KB Output is correct
4 Correct 150 ms 18212 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18212 KB Output is correct
2 Correct 5 ms 18212 KB Output is correct
3 Correct 5 ms 18212 KB Output is correct
4 Correct 4 ms 18212 KB Output is correct
5 Correct 8 ms 18212 KB Output is correct
6 Correct 26 ms 18212 KB Output is correct
7 Correct 388 ms 18212 KB Output is correct
8 Correct 302 ms 18212 KB Output is correct
9 Correct 236 ms 18212 KB Output is correct
10 Correct 229 ms 18212 KB Output is correct
11 Correct 184 ms 18212 KB Output is correct
12 Correct 169 ms 18212 KB Output is correct
13 Correct 164 ms 18212 KB Output is correct