Submission #378839

#	Time	Username	Problem	Language	Result	Execution time	Memory
378839		8e7	Regions (IOI09_regions)	C++14	13 / 100	207 ms	15084 KiB

regions

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define maxn 200005
#define maxc 25005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int siz = 128;
vector<int> adj[maxn], pos[maxc], node[maxc];
int col[maxc], cnt[maxc], ind[1000], cor[maxc];

int ans[505][maxc], lef[maxn], rig[maxn];

int cur = 0, num = 0, c = 0;
void dfs(int n, int par) {
	lef[n] = c++;
	ans[cur][col[n]] += num;
	if (col[n] == ind[cur]) num++;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n);
		}
	}
	rig[n] = c;
	if (col[n] == ind[cur]) num--;
}
int main() {
	io
	int n, r, q;
	cin >> n >> r >> q;
	cin >> col[1];
	cnt[col[1]]++;
	node[col[1]].push_back(1);
	for (int i = 2;i <= n;i++) {
		int p;
		cin >> p >> col[i];
		adj[p].push_back(i);
		adj[i].push_back(p);
		node[col[i]].push_back(i);
		cnt[col[i]]++;
	}
	dfs(1, 0);
	int id = 0;
	for (int i = 1;i <= r;i++) {
		if (cnt[i] >= 500) {
			ind[id] = i;
			cor[i] = id;
			cur = id;
			c = 0;
			dfs(1, 0);
			id++;
		}
	}
	for (int i = 1;i <= n;i++) {
		pos[col[i]].push_back(lef[i]);
		//cout << col[i] << "  " << lef[i] << endl;
		//cout << lef[i] << " " << rig[i] << endl;
	}
	for (int i = 1;i <= r;i++) {
		sort(pos[i].begin(), pos[i].end());
		/*
		cout << i << ": " << endl;
		for (int v:pos[i]) cout << v<< " ";
		cout << endl;
		*/
	}
	for (int i = 0;i < q;i++) {
		int r1, r2;
		cin >> r1 >> r2;
		if (cnt[r1] >= 500) cout << ans[cor[r1]][r2] << endl;
		else {
			int ans = 0;
			for (int v:node[r1]) {
				int rn = upper_bound(pos[r2].begin(), pos[r2].end(), rig[v] - 1) - pos[r2].begin();
				int ln = lower_bound(pos[r2].begin(), pos[r2].end(), lef[v]) - pos[r2].begin();
				//cout << v << ' ' << " " << rn << " " << ln << endl;
				ans += rn - ln;
			}
			cout << ans << endl;
		}
	}
}
/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
 */

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