oj.uz

Submission #53647

# Submission time Handle Problem Language Result Execution time Memory
53647 2018-06-30T15:40:34 Z baactree Regions (IOI09_regions) C++17
80 / 100
 7202 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 1200;
int cache[25005][sz];
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[a][inv[b]];
			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 114 ms 124536 KB Output is correct
2 Correct 106 ms 124632 KB Output is correct
3 Correct 104 ms 124648 KB Output is correct
4 Correct 102 ms 124648 KB Output is correct
5 Correct 105 ms 124740 KB Output is correct
6 Correct 109 ms 124808 KB Output is correct
7 Correct 117 ms 124808 KB Output is correct
8 Correct 119 ms 124812 KB Output is correct
9 Correct 140 ms 125324 KB Output is correct
10 Correct 208 ms 125324 KB Output is correct
11 Correct 273 ms 125556 KB Output is correct
12 Correct 252 ms 125952 KB Output is correct
13 Correct 266 ms 125952 KB Output is correct
14 Correct 472 ms 126348 KB Output is correct
15 Correct 489 ms 129340 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1577 ms 129412 KB Output is correct
2 Correct 1616 ms 129412 KB Output is correct
3 Correct 2604 ms 131072 KB Output is correct
4 Correct 247 ms 131072 KB Output is correct
5 Correct 492 ms 131072 KB Output is correct
6 Correct 627 ms 131072 KB Output is correct
7 Correct 974 ms 131072 KB Output is correct
8 Correct 1466 ms 131072 KB Output is correct
9 Correct 2839 ms 131072 KB Output is correct
10 Correct 4469 ms 131072 KB Output is correct
11 Correct 5216 ms 131072 KB Output is correct
12 Correct 5053 ms 131072 KB Output is correct
13 Correct 6219 ms 131072 KB Output is correct
14 Execution timed out 7202 ms 131072 KB Time limit exceeded (wall clock)
15 Execution timed out 7079 ms 131072 KB Time limit exceeded (wall clock)
16 Execution timed out 6577 ms 131072 KB Time limit exceeded (wall clock)
17 Execution timed out 6768 ms 131072 KB Time limit exceeded (wall clock)