제출 #1201991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1201991		NikoBaotic	Regions (IOI09_regions)	C++20	30 / 100	372 ms	25548 KiB

regions

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 200100;
const int R = 510;

int n, r, q;
int h[N];
int par[N];
vector<int> chi[N];
int in[N];
int out[N];
int timer;
int cnt[R][R];

vector<int>* dfs(int node) {
	timer++;
	in[node] = timer;

	vector<int>* cur = nullptr;

	for (int u : chi[node]) {
		vector<int>* v = dfs(u);

		if (cur == nullptr) {
			cur = v;
		} else {
			for (int i = 1; i < R; i++) {
				(*cur)[i] += (*v)[i];
			}

			delete(v);
		}
	}
	
	if (sz(chi[node]) == 0) {
		cur = new vector<int>(R);
	}
	
	for (int i = 1; i < R; i++) {
		cnt[h[node]][i] += (*cur)[i];
	}

	(*cur)[h[node]]++;

	out[node] = timer;

	return cur;
}

int main() {
	FIO;

	cin >> n >> r >> q;
	
	for (int i = 1; i <= n; i++) {
		if (i != 1) {
			cin >> par[i];

			chi[par[i]].pb(i);
		}

		cin >> h[i];
	}

	dfs(1);

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

		int ans = cnt[r1][r2];

		cout << ans << endl;
	}

	return 0;
}

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