oj.uz

Submission #53637

# Submission time Handle Problem Language Result Execution time Memory
53637 2018-06-30T15:25:38 Z baactree Regions (IOI09_regions) C++17
80 / 100
 7519 ms 87804 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> 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 53 ms 65784 KB Output is correct
2 Correct 58 ms 65844 KB Output is correct
3 Correct 64 ms 65920 KB Output is correct
4 Correct 58 ms 65920 KB Output is correct
5 Correct 64 ms 66088 KB Output is correct
6 Correct 75 ms 66156 KB Output is correct
7 Correct 74 ms 66156 KB Output is correct
8 Correct 80 ms 66156 KB Output is correct
9 Correct 112 ms 66568 KB Output is correct
10 Correct 134 ms 66696 KB Output is correct
11 Correct 145 ms 66872 KB Output is correct
12 Correct 141 ms 67388 KB Output is correct
13 Correct 257 ms 67516 KB Output is correct
14 Correct 370 ms 67928 KB Output is correct
15 Correct 414 ms 70460 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1672 ms 71100 KB Output is correct
2 Correct 1908 ms 71100 KB Output is correct
3 Correct 2611 ms 72892 KB Output is correct
4 Correct 310 ms 72892 KB Output is correct
5 Correct 427 ms 72892 KB Output is correct
6 Correct 678 ms 72892 KB Output is correct
7 Correct 922 ms 72892 KB Output is correct
8 Correct 1545 ms 75708 KB Output is correct
9 Correct 2582 ms 77116 KB Output is correct
10 Correct 5225 ms 81744 KB Output is correct
11 Correct 6463 ms 81744 KB Output is correct
12 Correct 6106 ms 81744 KB Output is correct
13 Correct 6714 ms 81744 KB Output is correct
14 Execution timed out 7519 ms 81744 KB Time limit exceeded (wall clock)
15 Execution timed out 7512 ms 82764 KB Time limit exceeded (wall clock)
16 Execution timed out 7202 ms 87804 KB Time limit exceeded (wall clock)
17 Execution timed out 7073 ms 87804 KB Time limit exceeded (wall clock)