oj.uz

Submission #43357

# Submission time Handle Problem Language Result Execution time Memory
43357 2018-03-14T14:34:10 Z szawinis Synchronization (JOI13_synchronization) C++14
100 / 100
 282 ms 73156 KB 
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define repi(i, a, b) for(int i = a; i <= b; i++)
#define drep(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
const int N = 1 << 18;

int n, m, q, u[N], v[N], d[N], s[N], e[N], ord[N], res[N], last[N];
bool state[N];
vector<int> g[N];
void dfs(int u, int p) {
	static int idx = 0;
	s[u] = ++idx;
	ord[s[u]] = u;
	for(int v: g[u]) if(v != p) d[v] = d[u] + 1, dfs(v, u);
	e[u] = idx;
}
int t[2*N];
void build(int i = 1, int l = 0, int r = N-1) {
	if(l == r) {
		t[i] = e[ord[l]];
		return;
	}
	int mid = l+r >> 1;
	build(i<<1, l, mid);
	build(i<<1|1, mid+1, r);
	t[i] = max(t[i<<1], t[i<<1|1]);
}
void update(int targ, int val, int i = 1, int l = 0, int r = N-1) {
	if(l == r) {
		t[i] = val;
		return;
	}
	int mid = l+r >> 1;
	if(targ <= mid) update(targ, val, i<<1, l, mid);
	else update(targ, val, i<<1|1, mid+1, r);
	t[i] = max(t[i<<1], t[i<<1|1]);
}
int get_root(int tl, int tr, int i = 1, int l = 0, int r = N-1) {
	if(l > tl || t[i] < tr) return -1;
	if(l == r) return ord[l];
	int mid = l+r >> 1, ret = get_root(tl, tr, i<<1|1, mid+1, r);
	if(ret != -1) return ret;
	return get_root(tl, tr, i<<1, l, mid);
}
int main() {
	scanf("%d %d %d", &n, &m, &q);
	rep(i, 1, n) {
		scanf("%d %d", u+i, v+i);
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(1, 0);
	build();
	fill(res+1, res+n+1, 1);
	rep(zz, 0, m) {
		int i; scanf("%d", &i);
		if(d[u[i]] > d[v[i]]) swap(u[i], v[i]);
		int root = get_root(s[u[i]], e[u[i]]);
		if(!state[i]) {
			res[root] += res[v[i]] - last[v[i]];
			update(s[v[i]], -1);
		} else {
			res[v[i]] = res[root];
			last[v[i]] = res[root];
			update(s[v[i]], e[v[i]]);
		}
		state[i] ^= 1;
	}
	rep(zz, 0, q) {
		int vert; scanf("%d", &vert);
		printf("%d\n", res[get_root(s[vert], e[vert])]);
	}
}

Compilation message

synchronization.cpp: In function 'void build(int, int, int)':
synchronization.cpp:24:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
synchronization.cpp: In function 'void update(int, int, int, int, int)':
synchronization.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
synchronization.cpp: In function 'int get_root(int, int, int, int, int)':
synchronization.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1, ret = get_root(tl, tr, i<<1|1, mid+1, r);
             ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:47:31: 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:49:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", u+i, v+i);
                           ^
synchronization.cpp:57:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int i; scanf("%d", &i);
                         ^
synchronization.cpp:71:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int vert; scanf("%d", &vert);
                               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8568 KB Output is correct
2 Correct 10 ms 8676 KB Output is correct
3 Correct 10 ms 8676 KB Output is correct
4 Correct 10 ms 8676 KB Output is correct
5 Correct 10 ms 8716 KB Output is correct
6 Correct 11 ms 9028 KB Output is correct
7 Correct 24 ms 9772 KB Output is correct
8 Correct 26 ms 9980 KB Output is correct
9 Correct 25 ms 10292 KB Output is correct
10 Correct 225 ms 18384 KB Output is correct
11 Correct 244 ms 20684 KB Output is correct
12 Correct 196 ms 27588 KB Output is correct
13 Correct 172 ms 27588 KB Output is correct
14 Correct 176 ms 27588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 30852 KB Output is correct
2 Correct 119 ms 32736 KB Output is correct
3 Correct 98 ms 36588 KB Output is correct
4 Correct 109 ms 38332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 38332 KB Output is correct
2 Correct 11 ms 38332 KB Output is correct
3 Correct 11 ms 38332 KB Output is correct
4 Correct 10 ms 38332 KB Output is correct
5 Correct 11 ms 38332 KB Output is correct
6 Correct 12 ms 38332 KB Output is correct
7 Correct 29 ms 38332 KB Output is correct
8 Correct 251 ms 42096 KB Output is correct
9 Correct 212 ms 45080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 48000 KB Output is correct
2 Correct 133 ms 50064 KB Output is correct
3 Correct 131 ms 52636 KB Output is correct
4 Correct 137 ms 54872 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 54872 KB Output is correct
2 Correct 10 ms 54872 KB Output is correct
3 Correct 10 ms 54872 KB Output is correct
4 Correct 10 ms 54872 KB Output is correct
5 Correct 12 ms 54872 KB Output is correct
6 Correct 31 ms 54872 KB Output is correct
7 Correct 282 ms 54872 KB Output is correct
8 Correct 229 ms 60856 KB Output is correct
9 Correct 184 ms 60856 KB Output is correct
10 Correct 205 ms 61152 KB Output is correct
11 Correct 171 ms 66332 KB Output is correct
12 Correct 153 ms 68752 KB Output is correct
13 Correct 168 ms 73156 KB Output is correct