oj.uz

Submission #53634

# Submission time Handle Problem Language Result Execution time Memory
53634 2018-06-30T15:12:47 Z baactree Regions (IOI09_regions) C++17
85 / 100
 7638 ms 92340 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> idx[25005];
vector<pair<int, int> > vec[25005];
int vn;
void dfs(int now, int par) {
	idx[arr[now]].push_back(vn);
	le[now] = vn++;
	for (auto &there : adj[now]) {
		if (there == par)continue;
		dfs(there, now);
	}
	ri[now] = vn++;
	vec[arr[now]].emplace_back(le[now], 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[a] < sz) {
			int &ans = cache[inv[a]][b];
			if (ans == -1) {
				ans = 0;
				for (auto x : vec[a]) {
					int le = x.first;
					int ri = x.second;
					ans += upper_bound(idx[b].begin(), idx[b].end(), ri) - lower_bound(idx[b].begin(), idx[b].end(), le);
				}
			}
			printf("%d\n", ans);
			fflush(stdout);
		}
		else {
			int ans = 0;
			for (auto x : vec[a]) {
				int le = x.first;
				int ri = x.second;
				ans += upper_bound(idx[b].begin(), idx[b].end(), ri) - lower_bound(idx[b].begin(), idx[b].end(), le);
			}
			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:47: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 54 ms 65144 KB Output is correct
2 Correct 62 ms 65204 KB Output is correct
3 Correct 53 ms 65280 KB Output is correct
4 Correct 55 ms 65280 KB Output is correct
5 Correct 56 ms 65356 KB Output is correct
6 Correct 64 ms 65484 KB Output is correct
7 Correct 83 ms 65644 KB Output is correct
8 Correct 92 ms 65644 KB Output is correct
9 Correct 93 ms 66080 KB Output is correct
10 Correct 161 ms 66080 KB Output is correct
11 Correct 226 ms 66336 KB Output is correct
12 Correct 182 ms 66976 KB Output is correct
13 Correct 230 ms 66980 KB Output is correct
14 Correct 401 ms 67360 KB Output is correct
15 Correct 422 ms 71084 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1743 ms 71084 KB Output is correct
2 Correct 1881 ms 71084 KB Output is correct
3 Correct 2475 ms 73404 KB Output is correct
4 Correct 313 ms 73404 KB Output is correct
5 Correct 412 ms 73404 KB Output is correct
6 Correct 583 ms 73404 KB Output is correct
7 Correct 791 ms 73404 KB Output is correct
8 Correct 1274 ms 76996 KB Output is correct
9 Correct 2557 ms 76996 KB Output is correct
10 Correct 4312 ms 83272 KB Output is correct
11 Correct 5469 ms 83272 KB Output is correct
12 Correct 5626 ms 83272 KB Output is correct
13 Correct 6454 ms 83272 KB Output is correct
14 Correct 7454 ms 83272 KB Output is correct
15 Execution timed out 7638 ms 83424 KB Time limit exceeded (wall clock)
16 Execution timed out 7483 ms 92340 KB Time limit exceeded (wall clock)
17 Execution timed out 7322 ms 92340 KB Time limit exceeded (wall clock)