제출 #648829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
648829		ymm	Regions (IOI09_regions)	C++17	100 / 100	4383 ms	30116 KiB

regions

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
 
const int S = 512;
const int N = 200'010 + S;
const int R = 25'010 + S;
int reg[N];
vector<int> reg_st_list[R];
vector<int> reg_list[R];
int cnt_reg[R];
int comp_big[R];
vector<int> big_list;
int ans_big[N/S][R];
int cnt_anc[R];
vector<int> A[N];
int st[N], ft[N];
int n, r, q;

void dfs(int v, int &t)
{
	st[v] = t++;
	reg_st_list[reg[v]].push_back(st[v]);
	for (int big : big_list)
		ans_big[comp_big[big]][reg[v]] += cnt_anc[big];
	cnt_anc[reg[v]]++;
	for (int u : A[v])
		dfs(u, t);
	cnt_anc[reg[v]]--;
	ft[v] = t;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> r >> q;
	cin >> reg[0];
	--reg[0];
	Loop (i,1,n) {
		int p;
		cin >> p >> reg[i];
		--reg[i];
		A[p-1].push_back(i);
	}
	Loop (i,0,n) {
		reg_list[reg[i]].push_back(i);
		cnt_reg[reg[i]]++;
	}
	Loop (i,0,r) {
		if (cnt_reg[i] >= S) {
			comp_big[i] = big_list.size();
			big_list.push_back(i);
		}
	}
	dfs(0, *new int(0));
	while (q--) {
		int r1, r2;
		cin >> r1 >> r2;
		--r1; --r2;
		if (cnt_reg[r1] >= S) {
			cout << ans_big[comp_big[r1]][r2] << '\n';
		} else {
			int ans = 0;
			for (int v : reg_list[r1]) {
				auto it1 = lower_bound(reg_st_list[r2].begin(), reg_st_list[r2].end(), st[v]);
				auto it2 = lower_bound(reg_st_list[r2].begin(), reg_st_list[r2].end(), ft[v]);
				ans += it2 - it1;
			}
			cout << ans << '\n';
		}
		cout.flush();
	}
}

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