oj.uz

Submission #53638

# Submission time Handle Problem Language Result Execution time Memory
53638 2018-06-30T15:26:16 Z baactree Regions (IOI09_regions) C++17
80 / 100
 7684 ms 127056 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 1000;
int cache[sz][25005];
pair<int, int> cnt[25005];
int inv[25005];
int le[200005], ri[200005];
vector<int> lv[25005], rv[25005];
vector<int> vec[25005];
int vn;
void dfs(int now, int par) {
	vec[arr[now]].push_back(now);
	le[now] = vn++;
	lv[arr[now]].push_back(le[now]);
	for (auto &there : adj[now]) {
		if (there == par)continue;
		dfs(there, now);
	}
	ri[now] = vn++;
	rv[arr[now]].push_back(ri[now]);
}
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);
		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);
		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(), le[x]) - lv[a].begin())
					- (lower_bound(rv[a].begin(), rv[a].end(), le[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(), le[x]) - lv[a].begin())
				- (lower_bound(rv[a].begin(), rv[a].end(), le[x]) - rv[a].begin());
			printf("%d\n", ans);
			fflush(stdout);
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:26: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:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &arr[1]);
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:31: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:48: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 82 ms 104892 KB Output is correct
2 Correct 84 ms 104892 KB Output is correct
3 Correct 86 ms 105068 KB Output is correct
4 Correct 102 ms 105068 KB Output is correct
5 Correct 88 ms 105068 KB Output is correct
6 Correct 95 ms 105124 KB Output is correct
7 Correct 92 ms 105140 KB Output is correct
8 Correct 115 ms 105200 KB Output is correct
9 Correct 108 ms 105632 KB Output is correct
10 Correct 150 ms 105760 KB Output is correct
11 Correct 207 ms 106036 KB Output is correct
12 Correct 212 ms 106640 KB Output is correct
13 Correct 246 ms 106684 KB Output is correct
14 Correct 402 ms 107068 KB Output is correct
15 Correct 349 ms 109612 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1658 ms 110184 KB Output is correct
2 Correct 2274 ms 110184 KB Output is correct
3 Correct 2777 ms 111996 KB Output is correct
4 Correct 382 ms 111996 KB Output is correct
5 Correct 564 ms 111996 KB Output is correct
6 Correct 766 ms 111996 KB Output is correct
7 Correct 630 ms 111996 KB Output is correct
8 Correct 1352 ms 114844 KB Output is correct
9 Correct 2968 ms 116296 KB Output is correct
10 Correct 5437 ms 120984 KB Output is correct
11 Correct 6365 ms 120984 KB Output is correct
12 Correct 5884 ms 120984 KB Output is correct
13 Correct 6804 ms 120984 KB Output is correct
14 Execution timed out 7684 ms 120984 KB Time limit exceeded (wall clock)
15 Execution timed out 7631 ms 121964 KB Time limit exceeded (wall clock)
16 Execution timed out 7384 ms 127056 KB Time limit exceeded (wall clock)
17 Execution timed out 7398 ms 127056 KB Time limit exceeded (wall clock)