oj.uz

Submission #53650

# Submission time Handle Problem Language Result Execution time Memory
53650 2018-06-30T15:42:41 Z baactree Regions (IOI09_regions) C++17
55 / 100
 5307 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 3000;
int cache[sz][25005];
pair<int, int> cnt[25005];
int inv[25005];
vector<int> lv[25005], rv[25005], vec[25005];
int vn;
void dfs(int now, int par) {
	vec[arr[now]].push_back(vn);
	lv[arr[now]].push_back(vn++);
	for (auto &there : adj[now]) {
		if (there == par)continue;
		dfs(there, now);
	}
	rv[arr[now]].push_back(vn++);
}
int main() {
	scanf("%d%d%d", &n, &r, &q);
	scanf("%d", &arr[1]);
	cnt[arr[1]].first++;
	for (int i = 2; i <= n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].push_back(i);
		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);
		if (inv[b] < sz) {
			int &ans = cache[inv[b]][a];
			if (ans == -1) {
				ans = 0;
				for (auto x : vec[b])
					ans += (lower_bound(lv[a].begin(), lv[a].end(), x) - lv[a].begin())
					- (lower_bound(rv[a].begin(), rv[a].end(), x) - rv[a].begin());
			}
			printf("%d\n", ans);
			fflush(stdout);
		}
		else {
			int ans = 0;
			for (auto x : vec[b])
				ans += (lower_bound(lv[a].begin(), lv[a].end(), x) - lv[a].begin())
				- (lower_bound(rv[a].begin(), rv[a].end(), x) - rv[a].begin());
			printf("%d\n", ans);
			fflush(stdout);
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &r, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &arr[1]);
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 131072 KB Output is correct
2 Correct 529 ms 131072 KB Output is correct
3 Correct 548 ms 131072 KB Output is correct
4 Correct 497 ms 131072 KB Output is correct
5 Correct 495 ms 131072 KB Output is correct
6 Correct 590 ms 131072 KB Output is correct
7 Correct 551 ms 131072 KB Output is correct
8 Correct 569 ms 131072 KB Output is correct
9 Correct 579 ms 131072 KB Output is correct
10 Correct 612 ms 131072 KB Output is correct
11 Correct 575 ms 131072 KB Output is correct
12 Correct 622 ms 131072 KB Output is correct
13 Correct 627 ms 131072 KB Output is correct
14 Correct 777 ms 131072 KB Output is correct
15 Correct 779 ms 131072 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2176 ms 131072 KB Output is correct
2 Correct 2318 ms 131072 KB Output is correct
3 Correct 2923 ms 131072 KB Output is correct
4 Correct 1043 ms 131072 KB Output is correct
5 Correct 1245 ms 131072 KB Output is correct
6 Correct 1162 ms 131072 KB Output is correct
7 Correct 1442 ms 131072 KB Output is correct
8 Correct 2371 ms 131072 KB Output is correct
9 Execution timed out 3262 ms 131072 KB Time limit exceeded (wall clock)
10 Execution timed out 4463 ms 131072 KB Time limit exceeded (wall clock)
11 Execution timed out 4874 ms 131072 KB Time limit exceeded (wall clock)
12 Execution timed out 5114 ms 131072 KB Time limit exceeded (wall clock)
13 Execution timed out 5307 ms 131072 KB Time limit exceeded (wall clock)
14 Execution timed out 4826 ms 131072 KB Time limit exceeded (wall clock)
15 Execution timed out 4719 ms 131072 KB Time limit exceeded (wall clock)
16 Execution timed out 4759 ms 131072 KB Time limit exceeded (wall clock)
17 Execution timed out 4388 ms 131072 KB Time limit exceeded (wall clock)