제출 #924982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924982		josanneo22	Regions (IOI09_regions)	C++17	10 / 100	8101 ms	22588 KiB

regions

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int _ = 2E5 + 500;
int r[_], N, R, Q, vis[_];
vector<int> child[_], officer[_];
void dfs(int u){
	vis[u] = 1;
	for(auto & v : child[u]) 
		dfs(v);
}
i64 work(int x, int y){
	i64 ans = 0;
	for(auto person : officer[x]){
		dfs(person);
		for(int i = 1; i <= N; i++){
			if(vis[i] && r[i] == y) 
				ans++;
			vis[i] = 0;
		}
	}
	
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> N >> R >> Q;
	cin >> r[1];
	officer[r[1]].push_back(1);
	for(int i = 2; i <= N; i++){
		int p; cin >> p >> r[i];
		child[p].push_back(i);
		officer[r[i]].push_back(i);
	}
	while(Q--){
		int r1, r2; cin >> r1 >> r2;
		i64 ans = work(r1, r2);
		cout << ans << endl;
	}
}

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