oj.uz

Submission #100888

# Submission time Handle Problem Language Result Execution time Memory
100888 2019-03-15T03:06:39 Z square1001 Synchronization (JOI13_synchronization) C++14
30 / 100
 8000 ms 24484 KB 
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
vector<int> solve_30pts(int N, int M, int Q, vector<int> X, vector<int> Y, vector<int> seq, vector<int> query) {
	vector<int> ans(Q);
	vector<int> par(N);
	vector<vector<int> > G(N);
	for(int i = 0; i < N - 1; ++i) {
		G[X[i]].push_back(Y[i]);
		G[Y[i]].push_back(X[i]);
	}
	function<void(int, int)> dfs = [&](int pos, int pre) {
		par[pos] = pre;
		for(int i : G[pos]) {
			if(i != pre) dfs(i, pos);
		}
	};
	vector<vector<int> > g(N - 1);
	for(int i = 0; i < M; ++i) {
		g[seq[i]].push_back(i);
	}
	for(int i = 0; i < Q; ++i) {
		dfs(query[i], -1);
		vector<int> pindex(N, -1);
		for(int j = 0; j < N - 1; ++j) {
			if(par[X[j]] == Y[j]) pindex[X[j]] = j;
			else pindex[Y[j]] = j;
		}
		function<int(int, int, int)> calc = [&](int pos, int pre, int timing) {
			int ans = 1;
			for(int i : G[pos]) {
				if(i == pre) continue;
				int ptr = lower_bound(g[pindex[i]].begin(), g[pindex[i]].end(), timing) - g[pindex[i]].begin();
				if(ptr % 2 == 1) ans += calc(i, pos, timing);
				else if(ptr != 0) ans += calc(i, pos, g[pindex[i]][ptr - 1]);
			}
			return ans;
		};
		ans[i] = calc(query[i], -1, M);
	}
	return ans;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, M, Q;
	cin >> N >> M >> Q;
	vector<int> X(N - 1), Y(N - 1), seq(M), query(Q);
	for(int i = 0; i < N - 1; ++i) {
		cin >> X[i] >> Y[i]; --X[i],--Y[i];
	}
	for(int i = 0; i < M; ++i) {
		cin >> seq[i]; --seq[i];
	}
	for(int i = 0; i < Q; ++i) {
		cin >> query[i]; --query[i];
	}
	vector<int> ans = solve_30pts(N, M, Q, X, Y, seq, query);
	for(int i : ans) {
		cout << i << '\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 10 ms 1792 KB Output is correct
8 Correct 15 ms 1792 KB Output is correct
9 Correct 10 ms 1792 KB Output is correct
10 Correct 129 ms 15068 KB Output is correct
11 Correct 142 ms 15032 KB Output is correct
12 Correct 116 ms 18552 KB Output is correct
13 Correct 217 ms 15344 KB Output is correct
14 Correct 123 ms 14628 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 21336 KB Output is correct
2 Correct 88 ms 18596 KB Output is correct
3 Correct 75 ms 24484 KB Output is correct
4 Correct 63 ms 22904 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 16 ms 640 KB Output is correct
7 Correct 1458 ms 2600 KB Output is correct
8 Execution timed out 8018 ms 22520 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8025 ms 22468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 25 ms 512 KB Output is correct
6 Correct 4357 ms 2176 KB Output is correct
7 Execution timed out 8071 ms 16464 KB Time limit exceeded
8 Halted 0 ms 0 KB -