Submission #53638

#	Time	Username	Problem	Language	Result	Execution time	Memory
53638		baactree	Regions (IOI09_regions)	C++17	80 / 100	7684 ms	127056 KiB

regions

#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 1000;
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 (stderr)

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