Submission #1189126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189126		DON_F	Regions (IOI09_regions)	C++20	100 / 100	2641 ms	111124 KiB

regions

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define L(i, b, e) for (int i = b; i < e; ++i)
#define R(i, b, e) for (int i = b; i >= e; --i)
#define pb emplace_back
#define vi vector<int>
#define sz(x) ((int) x.size())
const int N = 2e5 + 7;
int n, m;
vi g[N];
int r[N];
int st[N], ed[N];
int tim = 0;
vi s[N], e[N];
vi t[N];

void dfs(int x){
	st[x] = tim;
	tim++;
	s[r[x]].pb(st[x]);
	t[r[x]].pb(x);
	for (auto &i : g[x]){
		dfs(i);
	}
	ed[x] = tim - 1;
	e[r[x]].pb(ed[x]);
}

int k = 0;
int id[N];
vi c[N];
vector<vi> cnt;

void dfs2(int x){
	for (auto &i : g[x]){
		dfs2(i);
		L(j, 0, k){
			c[x][j] += c[i][j];
		}
	}
	if (id[r[x]] != -1){
		L(j, 0, k)cnt[id[r[x]]][j] += c[x][j];
		c[x][id[r[x]]]++;
	}
}

int q;

int main(){
    cin >> n >> m >> q;
    cin >> r[0];
    L(i, 1, n){
		int p;
		cin >> p >> r[i];
		p--;
		g[p].pb(i);
	}
	dfs(0);
	int sq = (int) sqrt(n);
	memset(id, -1, sizeof(id));
	L(i, 1, m + 1){
		if (sz(s[i]) >= sq){
			id[i] = k;
			k++;
		}
	}
	L(i, 0, n)c[i].resize(k + 1);
	cnt = vector<vi> (k + 1, vi(k + 1));
	dfs2(0);
	L(i, 0, q){
		int a, b;
		cin >> a >> b;
		if (min(sz(s[a]), sz(s[b])) >= sq){
			cout << cnt[id[a]][id[b]] << endl;
		}else if (sz(s[a]) < sq){
			int ans = 0;
			for (auto &j : t[a]){
				int l = upper_bound(all(s[b]), st[j]) - s[b].begin();
				int r = upper_bound(all(s[b]), ed[j]) - s[b].begin();
				ans += r - l;
			}
			cout << ans << endl;
		}else{
			int ans = 0;
			for (auto &j : t[b]){
				int l = lower_bound(all(e[a]), st[j]) - e[a].begin();
				int r = lower_bound(all(s[a]), st[j]) - s[a].begin();
				ans += sz(s[a]) - l - (sz(s[a]) - r);
			}
			cout << ans << endl;
		}
	}
}

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