oj.uz

Submission #113058

# Submission time Handle Problem Language Result Execution time Memory
113058 2019-05-23T13:14:05 Z maruii Synchronization (JOI13_synchronization) C++14
100 / 100
 269 ms 17912 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> edge[100001];
int dfn[100001], efn[100001], ifn[100001], dfnn;

void dfs(int x, int p) {
	dfn[x] = ++dfnn;
	ifn[dfnn] = x;
	for (auto i: edge[x]) {
		if (i != p)	dfs(i, x);
	}
	efn[x] = dfnn;
}

const int SIZE = 1 << 17;
struct ST {
	int V[SIZE << 1];
	
	void init(int nn, int s, int e) {
		if (s == e) {
			V[nn] = efn[ifn[s]];
			return;
		}
		int m = s + e >> 1;
		init(nn << 1, s, m);
		init(nn << 1 | 1, m + 1, e);
		V[nn] = max(V[nn << 1], V[nn << 1 | 1]);
	}

	void update(int nn, int ns, int ne, int x, int v) {
		if (ns > x || ne < x) return;
		if (ns == ne) {
			V[nn] = v;
			return;
		}
		int m = ns + ne >> 1;
		update(nn << 1, ns, m, x, v);
		update(nn << 1 | 1, m + 1, ne, x, v);
		V[nn] = max(V[nn << 1], V[nn << 1 | 1]);
	}

	int query(int nn, int ns, int ne, int s, int e) {
		if (ns > s || V[nn] < e) return 0;
		if (ns == ne) return ifn[ns];
		int m = ns + ne >> 1;
		int ret = query(nn << 1 | 1, m + 1, ne, s, e);
		if (ret) return ret;
		return query(nn << 1, ns, m, s, e);
	}
} seg;

int X[100002], Y[100002], T[100002], A[100002], B[100002];
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, M, Q; cin >> N >> M >> Q;
	for (int i = 1; i < N; ++i) {
		cin >> X[i] >> Y[i];
		edge[X[i]].push_back(Y[i]);
		edge[Y[i]].push_back(X[i]);
	}

	dfs(1, 0);
	seg.init(1, 1, N);
	fill(A, A + N + 1, 1);

	for (int i = 0; i < M; ++i) {
		int j; cin >> j;
		auto &x = X[j], &y = Y[j];
		if (dfn[x] < dfn[y]) swap(x, y);
		if (T[j]) {
			A[x] = B[x] = A[seg.query(1, 1, N, dfn[x], efn[x])];
			seg.update(1, 1, N, dfn[x], efn[x]);
		}
		else {
			seg.update(1, 1, N, dfn[x], 0);
			A[seg.query(1, 1, N, dfn[x], efn[x])] += A[x] - B[x];
		}
		T[j] ^= 1;
	}

	for (int i = 0; i < Q; ++i) {
		int x; cin >> x;
		cout << A[seg.query(1, 1, N, dfn[x], efn[x])] << '\n';
	}
	return 0;
}

Compilation message

synchronization.cpp: In member function 'void ST::init(int, int, int)':
synchronization.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~
synchronization.cpp: In member function 'void ST::update(int, int, int, int, int)':
synchronization.cpp:37:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns + ne >> 1;
           ~~~^~~~
synchronization.cpp: In member function 'int ST::query(int, int, int, int, int)':
synchronization.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns + ne >> 1;
           ~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 17 ms 3740 KB Output is correct
8 Correct 16 ms 3712 KB Output is correct
9 Correct 16 ms 3712 KB Output is correct
10 Correct 240 ms 12460 KB Output is correct
11 Correct 214 ms 12452 KB Output is correct
12 Correct 177 ms 17016 KB Output is correct
13 Correct 166 ms 12360 KB Output is correct
14 Correct 118 ms 11416 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 14328 KB Output is correct
2 Correct 92 ms 14232 KB Output is correct
3 Correct 76 ms 16120 KB Output is correct
4 Correct 80 ms 16092 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2792 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2756 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 19 ms 4224 KB Output is correct
8 Correct 221 ms 17784 KB Output is correct
9 Correct 196 ms 17804 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 17800 KB Output is correct
2 Correct 114 ms 17148 KB Output is correct
3 Correct 98 ms 17400 KB Output is correct
4 Correct 99 ms 17224 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 4 ms 2660 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 20 ms 3712 KB Output is correct
7 Correct 269 ms 13208 KB Output is correct
8 Correct 224 ms 17912 KB Output is correct
9 Correct 233 ms 13412 KB Output is correct
10 Correct 179 ms 12760 KB Output is correct
11 Correct 125 ms 15480 KB Output is correct
12 Correct 132 ms 15608 KB Output is correct
13 Correct 104 ms 17272 KB Output is correct