Submission #534325

#	Time	Username	Problem	Language	Result	Execution time	Memory
534325		Cantfindme	Regions (IOI09_regions)	C++17	100 / 100	4885 ms	45728 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 200010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;
const int len = 450;

int n, R, Q;
vector <int> adjlist[maxn];
vector <int> v[maxn], v2[maxn];
int ans[len+10][maxn];
int indx[maxn], rev[maxn], col[maxn];

int pre[maxn], post[maxn];

int co = 1;
void dfs(int x, int p) {
	pre[x] = co++;
	rev[pre[x]] = x;
	for (auto i: adjlist[x]) if (i != p) {
		dfs(i,x);
	}
	post[x] = co - 1;

}

int32_t main() {
	// ifstream cin("input.txt");

	cin >> n >> R >> Q;
	for (int i =1;i<=n;i++) {
		if (i == 1) {
			int x; cin >> x;
			col[i] = x;
			v[x].push_back(i);
		} else {
			int x, p; cin >> p >> x;
			col[i] = x;
			v[x].push_back(i);
			adjlist[p].push_back(i);
		}
	}
	dfs(1,-1);

	co = 0;
	for (int x = 1; x <= R; x++) {
		for (auto i: v[x]) {
			v2[x].push_back(pre[i]);
		}
		sort(all(v2[x]));

		if (v[x].size() >= len) {
			indx[x] = co; 
			vector <int> pref(n+2, 0);
			for (auto i: v[x]) {
				pref[pre[i]]++;
				pref[post[i]+1]--;
			}

			int cur = 0;
			for (int j = 1; j<= n;j++) {
				cur += pref[j];
				int child = rev[j];
				ans[indx[x]][col[child]] += cur;
			}

			co++;
		}
	}

	for (int q=0;q<Q;q++) {
		int r1, r2; cin >> r1 >> r2;
		if (v[r1].size() >= len) {
			cout << ans[indx[r1]][r2] << "\n";
		} else {
			int rans = 0;
			for (auto i: v[r1]) { //sqrt(N)
				int lb = lower_bound(all(v2[r2]), pre[i]) - v2[r2].begin();
				int rb = upper_bound(all(v2[r2]), post[i]) - v2[r2].begin();
				rans += rb - lb;
			}
			cout << rans << "\n";
		}
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85