제출 #916004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916004		Juanchoki	Regions (IOI09_regions)	C++14	19 / 100	8096 ms	26520 KiB

regions

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200001];
int region[200001];
vector<int> zona[25001];
vector<int> euler;
int ini[200001], fin[200001], cnt = 0;
void dfs(int nodo)
{
	euler.push_back(nodo);
	ini[nodo] = cnt++;
	for (int v: adj[nodo])
		dfs(v);
	euler.push_back(nodo);
	fin[nodo] = cnt++;
}
int main() 
{
	int n, r, q, a; cin >> n >> r >> q;
	cin >> region[1];
	zona[region[1]].push_back(1);
	for (int i = 2; i <= n; i++)
	{
		cin >> a;
		adj[a].push_back(i);
		cin >> a;
		region[i] = a;
		zona[a].push_back(i);
	}
	dfs(1);
	
	while (q--)
	{
		cin >> a >> r;
		int resp = 0;
		for (int pos: zona[a])
			for (int i = ini[pos]+1; i < fin[pos]; i++)
				if (region[euler[i]] == r) resp++;
		cout << resp/2 << endl;
	}
	
}

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