oj.uz

Submission #53645

# Submission time Handle Problem Language Result Execution time Memory
53645 2018-06-30T15:36:12 Z baactree Regions (IOI09_regions) C++17
60 / 100
 6131 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 1600;
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 204 ms 131072 KB Output is correct
2 Correct 211 ms 131072 KB Output is correct
3 Correct 233 ms 131072 KB Output is correct
4 Correct 213 ms 131072 KB Output is correct
5 Correct 234 ms 131072 KB Output is correct
6 Correct 222 ms 131072 KB Output is correct
7 Correct 227 ms 131072 KB Output is correct
8 Correct 251 ms 131072 KB Output is correct
9 Correct 248 ms 131072 KB Output is correct
10 Correct 284 ms 131072 KB Output is correct
11 Correct 347 ms 131072 KB Output is correct
12 Correct 368 ms 131072 KB Output is correct
13 Correct 425 ms 131072 KB Output is correct
14 Correct 513 ms 131072 KB Output is correct
15 Correct 537 ms 131072 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1615 ms 131072 KB Output is correct
2 Correct 1954 ms 131072 KB Output is correct
3 Correct 2685 ms 131072 KB Output is correct
4 Correct 556 ms 131072 KB Output is correct
5 Correct 604 ms 131072 KB Output is correct
6 Correct 1002 ms 131072 KB Output is correct
7 Correct 1123 ms 131072 KB Output is correct
8 Correct 1585 ms 131072 KB Output is correct
9 Correct 3079 ms 131072 KB Output is correct
10 Execution timed out 4590 ms 131072 KB Time limit exceeded (wall clock)
11 Execution timed out 5404 ms 131072 KB Time limit exceeded (wall clock)
12 Execution timed out 5776 ms 131072 KB Time limit exceeded (wall clock)
13 Execution timed out 6131 ms 131072 KB Time limit exceeded (wall clock)
14 Execution timed out 5419 ms 131072 KB Time limit exceeded (wall clock)
15 Execution timed out 5015 ms 131072 KB Time limit exceeded (wall clock)
16 Execution timed out 5228 ms 131072 KB Time limit exceeded (wall clock)
17 Execution timed out 4905 ms 131072 KB Time limit exceeded (wall clock)