oj.uz

Submission #53642

# Submission time Handle Problem Language Result Execution time Memory
53642 2018-06-30T15:32:07 Z baactree Regions (IOI09_regions) C++17
75 / 100
 7571 ms 68152 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 400;
int cache[sz][25005];
pair<int, int> cnt[25005];
int inv[25005];
int le[200005], ri[200005];
vector<int> lv[25005], rv[25005], 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);
		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:25: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:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &arr[1]);
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:30: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:46: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 43 ms 46244 KB Output is correct
2 Correct 42 ms 46244 KB Output is correct
3 Correct 42 ms 46252 KB Output is correct
4 Correct 48 ms 46252 KB Output is correct
5 Correct 47 ms 46340 KB Output is correct
6 Correct 56 ms 46516 KB Output is correct
7 Correct 70 ms 46516 KB Output is correct
8 Correct 73 ms 46516 KB Output is correct
9 Correct 110 ms 46988 KB Output is correct
10 Correct 125 ms 47012 KB Output is correct
11 Correct 149 ms 47316 KB Output is correct
12 Correct 200 ms 47760 KB Output is correct
13 Correct 234 ms 47760 KB Output is correct
14 Correct 378 ms 48188 KB Output is correct
15 Correct 331 ms 50748 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1606 ms 51388 KB Output is correct
2 Correct 2021 ms 51388 KB Output is correct
3 Correct 2774 ms 53312 KB Output is correct
4 Correct 332 ms 53312 KB Output is correct
5 Correct 418 ms 53312 KB Output is correct
6 Correct 657 ms 53312 KB Output is correct
7 Correct 880 ms 53312 KB Output is correct
8 Correct 1394 ms 56120 KB Output is correct
9 Correct 2675 ms 57096 KB Output is correct
10 Correct 4945 ms 62244 KB Output is correct
11 Correct 6392 ms 62244 KB Output is correct
12 Correct 6101 ms 62244 KB Output is correct
13 Execution timed out 7514 ms 62244 KB Time limit exceeded (wall clock)
14 Execution timed out 7495 ms 62244 KB Time limit exceeded (wall clock)
15 Execution timed out 7571 ms 63116 KB Time limit exceeded (wall clock)
16 Execution timed out 7421 ms 68152 KB Time limit exceeded (wall clock)
17 Execution timed out 7265 ms 68152 KB Time limit exceeded (wall clock)