제출 #1287284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287284		Jawad_Akbar_JJ	Regions (IOI09_regions)	C++17	95 / 100	8060 ms	41260 KiB

regions

#include <iostream>
#include <vector>

using namespace std;
const int N = 200'005, R = 25'005, K = 300;
int anc[505][R], desc[505][R], in[N], num[N], out[N], h[N], tot, cur;
vector<int> nei[N], occ[R];

void dfs(int u, int cl, int id, int soFar = 0){
	soFar += h[u] == cl, tot += h[u] == cl;
	anc[id][h[u]] += soFar;
	in[u] = ++cur;

	int now = tot;
	for (int i : nei[u])
		dfs(i, cl, id, soFar);

	desc[id][h[u]] += tot - now;
	out[u] = ++cur;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, r, q;
	cin>>n>>r>>q;

	for (int i=1, s;i<=n;i++){
		if (i - 1){
			cin>>s;
			nei[s].push_back(i);
		}
		cin>>h[i];
		occ[h[i]].push_back(i);
	}

	dfs(1, 0, 0);
	for (int i=1, vl = 0;i<=r;i++){
		if (occ[i].size() >= K)
			num[i] = ++vl, tot = 0, cur = 0, dfs(1, i, vl);
	}

	for (int i=1;i<=q;i++){
		int r1, r2, ans = 0;
		cin>>r1>>r2;

		if (occ[r1].size() >= K){
			cout<<anc[num[r1]][r2]<<'\n';
		}
		else if (occ[r2].size() >= K){
			cout<<desc[num[r2]][r1]<<'\n';
		}
		else{
			for (int k=0;k<occ[r2].size();k++){
				for (int j=0;j<occ[r1].size();j++){
					if (occ[r2][k] < occ[r1][j])
						break;
					if (in[occ[r1][j]] <= in[occ[r2][k]] and out[occ[r2][k]] <= out[occ[r1][j]])
						ans++;
				}
			}
			cout<<ans<<'\n';
		}
		cout.flush();
	}
}

/*

6 3 4
1
1 2
1 3
2 3
2 3
5 1

1 2

1 3

2 3

3 1




*/

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