제출 #924985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924985		josanneo22	Regions (IOI09_regions)	C++17	13 / 100	8096 ms	44984 KiB

regions

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

const int _ = 2E5 + 500;
int r[_], N, R, Q, vis[_], val[504][504], cal[504][504];
vector<int> child[_], officer[_];
void dfs(int u){
	vis[u]++;
	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(r[i] == y)
			ans += (vis[i]);
		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;
		if(cal[r1][r2] == false){
			ans = work(r1, r2);
			val[r1][r2] = ans;
			cal[r1][r2] = true;
		}
		else ans = val[r1][r2];
		cout << ans << endl;
	}
}

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