oj.uz

Submission #66154

# Submission time Handle Problem Language Result Execution time Memory
66154 2018-08-09T22:15:30 Z zadrga Synchronization (JOI13_synchronization) C++14
100 / 100
 350 ms 68664 KB 
#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:84: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:87: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:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &ind);
   ~~~~~^~~~~~~~~~~~
synchronization.cpp:130: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 4 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 6 ms 2832 KB Output is correct
6 Correct 6 ms 2852 KB Output is correct
7 Correct 20 ms 3808 KB Output is correct
8 Correct 20 ms 4068 KB Output is correct
9 Correct 20 ms 4212 KB Output is correct
10 Correct 262 ms 13388 KB Output is correct
11 Correct 350 ms 15672 KB Output is correct
12 Correct 257 ms 22492 KB Output is correct
13 Correct 169 ms 22492 KB Output is correct
14 Correct 185 ms 22492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 26208 KB Output is correct
2 Correct 132 ms 28100 KB Output is correct
3 Correct 98 ms 32040 KB Output is correct
4 Correct 105 ms 33744 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 33744 KB Output is correct
2 Correct 4 ms 33744 KB Output is correct
3 Correct 5 ms 33744 KB Output is correct
4 Correct 4 ms 33744 KB Output is correct
5 Correct 5 ms 33744 KB Output is correct
6 Correct 7 ms 33744 KB Output is correct
7 Correct 23 ms 33744 KB Output is correct
8 Correct 257 ms 37216 KB Output is correct
9 Correct 286 ms 40052 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 42924 KB Output is correct
2 Correct 146 ms 45604 KB Output is correct
3 Correct 156 ms 47908 KB Output is correct
4 Correct 137 ms 50264 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 50264 KB Output is correct
2 Correct 5 ms 50264 KB Output is correct
3 Correct 4 ms 50264 KB Output is correct
4 Correct 4 ms 50264 KB Output is correct
5 Correct 6 ms 50264 KB Output is correct
6 Correct 24 ms 50264 KB Output is correct
7 Correct 338 ms 50264 KB Output is correct
8 Correct 269 ms 56184 KB Output is correct
9 Correct 201 ms 56184 KB Output is correct
10 Correct 209 ms 56724 KB Output is correct
11 Correct 177 ms 61692 KB Output is correct
12 Correct 175 ms 64200 KB Output is correct
13 Correct 145 ms 68664 KB Output is correct