oj.uz

Submission #53657

# Submission time Handle Problem Language Result Execution time Memory
53657 2018-06-30T15:58:34 Z baactree Regions (IOI09_regions) C++17
100 / 100
 5562 ms 30656 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 467;
int dp[sz][25005];
int idx[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]);
	for (int i = 2; i <= n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].push_back(i);
		arr[i] = b;
	}
	dfs(1, 0);
	int cnt = 0;
	for (int i = 1; i <= r; i++) {
		if (vec[i].size() >= sz) {
			idx[i] = ++cnt;
			for (int j = 1; j <= r; j++) {
				int ans = 0;
				int lidx = 0;
				int ridx = 0;
				for (auto x : vec[i]) {
					while (lidx < lv[j].size() && lv[j][lidx] < x)lidx++;
					while (ridx < rv[j].size() && rv[j][ridx] < x)ridx++;
					ans += lidx - ridx;
				}
				dp[idx[i]][j] = ans;
			}
		}
	}

	while (q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		if (idx[b]) {
			printf("%d\n", dp[idx[b]][a]);
			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:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while (lidx < lv[j].size() && lv[j][lidx] < x)lidx++;
             ~~~~~^~~~~~~~~~~~~~
regions.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while (ridx < rv[j].size() && rv[j][ridx] < x)ridx++;
             ~~~~~^~~~~~~~~~~~~~
regions.cpp:21: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:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &arr[1]);
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:25: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:50: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 7 ms 6672 KB Output is correct
2 Correct 8 ms 6840 KB Output is correct
3 Correct 11 ms 6916 KB Output is correct
4 Correct 15 ms 6916 KB Output is correct
5 Correct 14 ms 6980 KB Output is correct
6 Correct 14 ms 7004 KB Output is correct
7 Correct 33 ms 7180 KB Output is correct
8 Correct 41 ms 7224 KB Output is correct
9 Correct 54 ms 7612 KB Output is correct
10 Correct 82 ms 7612 KB Output is correct
11 Correct 128 ms 7740 KB Output is correct
12 Correct 141 ms 8380 KB Output is correct
13 Correct 177 ms 8380 KB Output is correct
14 Correct 357 ms 8508 KB Output is correct
15 Correct 387 ms 11708 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2094 ms 11836 KB Output is correct
2 Correct 2550 ms 11836 KB Output is correct
3 Correct 3575 ms 13884 KB Output is correct
4 Correct 286 ms 13884 KB Output is correct
5 Correct 363 ms 13884 KB Output is correct
6 Correct 1014 ms 13884 KB Output is correct
7 Correct 1807 ms 13884 KB Output is correct
8 Correct 2292 ms 20748 KB Output is correct
9 Correct 2524 ms 20748 KB Output is correct
10 Correct 4457 ms 23740 KB Output is correct
11 Correct 5295 ms 23740 KB Output is correct
12 Correct 2631 ms 23740 KB Output is correct
13 Correct 3041 ms 23740 KB Output is correct
14 Correct 5035 ms 23740 KB Output is correct
15 Correct 5091 ms 23740 KB Output is correct
16 Correct 4533 ms 30460 KB Output is correct
17 Correct 5562 ms 30656 KB Output is correct