Submission #1137771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137771		sano	Regions (IOI09_regions)	C++17	3 / 100	3158 ms	29428 KiB

regions

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 1000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

vec<vec<int>> g;
vec<vec<int>> mp;
vec<int> k;

void dfs(int x, int f, int poc = 0, int pr = -1) {
	if (k[x] == f) poc++;
	else {
		mp.back()[k[x]] += poc;
	}
	trav(i, g[x]) {
		if (i == pr) continue;
		dfs(i, f, poc, x);
	}
	return;
}

vec<int> e1, e2;
int ti = 0;

void dfs2(int x, int pr = -1) {
	e1[x] = ti; ti++;
	trav(i, g[x]) {
		if (i == pr) continue;
		dfs2(i, x);
	}
	e2[x] = ti - 1;
	return;
}

void solve() {
	int n, r, q; cin >> n >> r >> q;
	k.resize(n); e1.resize(n); e2.resize(n);
	g.resize(n);
	cin >> k[0]; k[0]--;
	For(i, (n - 1)) {
		int a; cin >> a >> k[i + 1]; k[i + 1]--;
		a--;
		g[i+1].push_back(a);
		g[a].push_back(i+1);
	}
	vec<int> p(r, 0);
	vec<int> prazdny(r, 0);
	For(i, k.size()) p[k[i]]++;
	int odm = sqrt(n);
	vec<int> v(r, -1);
	For(i, p.size()) {
		if (p[i] > odm) {
			v[i] = mp.size();
			mp.push_back(prazdny);
			dfs(0, i);
		}
	}
	vec<vec<int>> vy(r);
	dfs2(0);
	For(i, n) {
		vy[k[i]].push_back(e1[i]);
	}
	For(i, vy.size()) sort(vy[i].begin(), vy[i].end());
	For(i, q) {
		int r1, r2; cin >> r1 >> r2; r1--; r2--;
		if (v[r1] == -1) {
			int vv = 0;
			trav(j, vy[r1]) {
				int q1 = lower_bound(vy[r2].begin(), vy[r2].end(), e1[j]) - vy[r2].begin();
				int q2 = upper_bound(vy[r2].begin(), vy[r2].end(), e2[j]) - vy[r2].begin();
				vv += q2 - q1;
			}
			cout << vv << endl;
		}
		else {
			cout << mp[v[r1]][r2] << endl;
		}
	}
	return;
}

signed main() {
	//ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t; 
	//cin >> t;
	t = 1;
	while (t--) {
		solve();
	}
	return 0;
}

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