제출 #916002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916002		Juanchoki	Regions (IOI09_regions)	C++14	30 / 100	5226 ms	14524 KiB

regions

#include <bits/stdc++.h>
using namespace std;
int mapa[501][501];
vector<int> adj[200001];
int region[200001];
vector<int> zona[501];
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);
	//for (int x: euler) cout << x << " " << region[x] << '\n';
	for (int i = 1; i <= 500; i++)
	{
		for (int pos: zona[i])
		{
			for (int j = ini[pos]+1; j < fin[pos]; j++)
			{
				mapa[i][region[euler[j]]]++;
			}
		}
	}
	while (q--)
	{
		cin >> a >> r;
		cout << mapa[a][r]/2 << endl;
	}
}

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