Submission #53657

#	Time	Username	Problem	Language	Result	Execution time	Memory
53657		baactree	Regions (IOI09_regions)	C++17	100 / 100	5562 ms	30656 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 85 / 85