oj.uz

Submission #53639

# Submission time Handle Problem Language Result Execution time Memory
53639 2018-06-30T15:28:18 Z baactree Regions (IOI09_regions) C++17
60 / 100
 6170 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 2000;
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 330 ms 131072 KB Output is correct
2 Correct 281 ms 131072 KB Output is correct
3 Correct 279 ms 131072 KB Output is correct
4 Correct 294 ms 131072 KB Output is correct
5 Correct 312 ms 131072 KB Output is correct
6 Correct 321 ms 131072 KB Output is correct
7 Correct 314 ms 131072 KB Output is correct
8 Correct 311 ms 131072 KB Output is correct
9 Correct 345 ms 131072 KB Output is correct
10 Correct 445 ms 131072 KB Output is correct
11 Correct 398 ms 131072 KB Output is correct
12 Correct 459 ms 131072 KB Output is correct
13 Correct 595 ms 131072 KB Output is correct
14 Correct 690 ms 131072 KB Output is correct
15 Correct 601 ms 131072 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2105 ms 131072 KB Output is correct
2 Correct 2277 ms 131072 KB Output is correct
3 Correct 3118 ms 131072 KB Output is correct
4 Correct 781 ms 131072 KB Output is correct
5 Correct 847 ms 131072 KB Output is correct
6 Correct 1034 ms 131072 KB Output is correct
7 Correct 1232 ms 131072 KB Output is correct
8 Correct 1975 ms 131072 KB Output is correct
9 Correct 4016 ms 131072 KB Output is correct
10 Execution timed out 4266 ms 131072 KB Time limit exceeded (wall clock)
11 Execution timed out 5317 ms 131072 KB Time limit exceeded (wall clock)
12 Execution timed out 6170 ms 131072 KB Time limit exceeded (wall clock)
13 Execution timed out 5715 ms 131072 KB Time limit exceeded (wall clock)
14 Execution timed out 5349 ms 131072 KB Time limit exceeded (wall clock)
15 Execution timed out 4593 ms 131072 KB Time limit exceeded (wall clock)
16 Execution timed out 5058 ms 131072 KB Time limit exceeded (wall clock)
17 Execution timed out 4981 ms 131072 KB Time limit exceeded (wall clock)