제출 #1082422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082422		Thunnus	Regions (IOI09_regions)	C++17	100 / 100	2632 ms	47748 KiB

regions

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size() 

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, r, q;
	cin >> n >> r >> q;
	const int SZ = ceil(sqrt(n));
	vi par(n), reg(n);
	vvi children(n), precalc(r), reg_tins(r), r2v(r);
	cin >> reg[0];
	reg[0]--;
	for(int i = 1; i < n; i++){
		cin >> par[i] >> reg[i];
		par[i]--, reg[i]--;
		children[par[i]].emplace_back(i);
	}

	vi tin(n), tout(n);
	int timer = 0;
	function<void(int)> euler = [&](int v) -> void {
		tin[v] = timer++;
		reg_tins[reg[v]].emplace_back(tin[v]);
		r2v[reg[v]].emplace_back(v);
		for(int &u : children[v]){
			euler(u);
		}
		tout[v] = timer - 1;
	};
	euler(0);

	int curreg = -1, curcnt = 0;
	function<void(int)> dfs = [&](int v) -> void {
		if(curreg == reg[v]){
			curcnt++;
		}
		else{
			precalc[curreg][reg[v]] += curcnt;
		}
		for(int &u : children[v]){
			dfs(u);
		}
		curcnt -= (curreg == reg[v]);
	};

	for(int i = 0; i < r; i++){
		if(sz(r2v[i]) >= SZ){
			curreg = i, curcnt = 0;
			precalc[i].resize(r);
			dfs(0);
		}
	}

	while(q--){
		int r1, r2;
		cin >> r1 >> r2;
		r1--, r2--;
		if(sz(r2v[r1]) >= SZ){
			cout << precalc[r1][r2] << endl;
		}
		else{
			int ans = 0;
			for(int &v : r2v[r1]){
				ans += upper_bound(reg_tins[r2].begin(), reg_tins[r2].end(), tout[v]) - lower_bound(reg_tins[r2].begin(), reg_tins[r2].end(), tin[v]);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

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