oj.uz

Submission #53635

# Submission time Handle Problem Language Result Execution time Memory
53635 2018-06-30T15:14:43 Z baactree Regions (IOI09_regions) C++17
80 / 100
 7552 ms 92348 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 600;
int cache[sz][25005];
pair<int, int> cnt[25005];
int inv[25005];
int le[200005], ri[200005];
vector<int> idx[25005];
vector<pair<int, int> > vec[25005];
int vn;
void dfs(int now, int par) {
	idx[arr[now]].push_back(vn);
	le[now] = vn++;
	for (auto &there : adj[now]) {
		if (there == par)continue;
		dfs(there, now);
	}
	ri[now] = vn++;
	vec[arr[now]].emplace_back(le[now], ri[now]);
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie();
	//scanf("%d%d%d", &n, &r, &q);
	cin >> n >> r >> q;
	//scanf("%d", &arr[1]);
	cin >> arr[1];
	cnt[arr[1]].first++;
	for (int i = 2; i <= n; i++) {
		int a, b;
		//scanf("%d%d", &a, &b);
		cin >> a >> b;
		adj[a].push_back(i);
		adj[i].push_back(a);
		arr[i] = b;
		cnt[arr[i]].first++;
	}
	for (int i = 0; i < 25005; i++)
		cnt[i].second = i;
	sort(cnt, cnt + 25005, [&](pair<int, int> &a, pair<int, int> &b) {
		return a > b;
	});
	for (int i = 0; i < 25005; i++)
		inv[cnt[i].second] = i;
	dfs(1, 0);
	memset(cache, -1, sizeof(cache));
	while (q--) {
		int a, b;
		//scanf("%d%d", &a, &b);
		cin >> a >> b;
		if (inv[a] < sz) {
			int &ans = cache[inv[a]][b];
			if (ans == -1) {
				ans = 0;
				for (auto &x : vec[a]) {
					int le = x.first;
					int ri = x.second;
					ans += upper_bound(idx[b].begin(), idx[b].end(), ri) - lower_bound(idx[b].begin(), idx[b].end(), le);
				}
			}
			//printf("%d\n", ans);
			cout << ans << '\n';
			fflush(stdout);
		}
		else {
			int ans = 0;
			for (auto &x : vec[a]) {
				int le = x.first;
				int ri = x.second;
				ans += upper_bound(idx[b].begin(), idx[b].end(), ri) - lower_bound(idx[b].begin(), idx[b].end(), le);
			}
			//printf("%d\n", ans);
			cout << ans << '\n';
			fflush(stdout);
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 65144 KB Output is correct
2 Correct 54 ms 65204 KB Output is correct
3 Correct 55 ms 65280 KB Output is correct
4 Correct 57 ms 65316 KB Output is correct
5 Correct 62 ms 65444 KB Output is correct
6 Correct 57 ms 65472 KB Output is correct
7 Correct 78 ms 65472 KB Output is correct
8 Correct 83 ms 65548 KB Output is correct
9 Correct 96 ms 66052 KB Output is correct
10 Correct 132 ms 66060 KB Output is correct
11 Correct 176 ms 66364 KB Output is correct
12 Correct 183 ms 67004 KB Output is correct
13 Correct 242 ms 67004 KB Output is correct
14 Correct 338 ms 67388 KB Output is correct
15 Correct 341 ms 71100 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1421 ms 71100 KB Output is correct
2 Correct 1724 ms 71100 KB Output is correct
3 Correct 2340 ms 73400 KB Output is correct
4 Correct 319 ms 73400 KB Output is correct
5 Correct 428 ms 73400 KB Output is correct
6 Correct 479 ms 73400 KB Output is correct
7 Correct 942 ms 73400 KB Output is correct
8 Correct 1444 ms 76988 KB Output is correct
9 Correct 2360 ms 76988 KB Output is correct
10 Correct 4771 ms 83260 KB Output is correct
11 Correct 5101 ms 83260 KB Output is correct
12 Correct 5155 ms 83260 KB Output is correct
13 Correct 6324 ms 83260 KB Output is correct
14 Execution timed out 7549 ms 83260 KB Time limit exceeded (wall clock)
15 Execution timed out 7416 ms 83380 KB Time limit exceeded (wall clock)
16 Execution timed out 7552 ms 92348 KB Time limit exceeded (wall clock)
17 Incorrect 7333 ms 92348 KB Unexpected end of file - int32 expected