Submission #113164

#	Time	Username	Problem	Language	Result	Execution time	Memory
113164		joseacaz	Regions (IOI09_regions)	C++17	0 / 100	8055 ms	121444 KiB

regions

#include <iostream>
#include <vector>
#define MAXN 200005
#define MAXR 25005

using namespace std;
typedef long long lld;

lld N, R, Q, region[MAXN], supervisor[MAXN], c, answer[505][MAXR], a, b;
vector < lld > Graph[MAXN];

void dfs ( lld reg, lld node )
{
	answer[reg][region[node]] += c;

	if ( region[node] == reg )
		c++;
	for ( auto i : Graph[node] )
		dfs ( reg, i );
	if ( region[node] == reg )
		c--;
}

int main ()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> R >> Q;
	cin >> region[1];
	for ( lld i = 2; i <= N; i++ )
	{
		cin >> supervisor[i] >> region[i];
		Graph[supervisor[i]].push_back ( i );
	}

	for ( lld i = 1; i <= 500; i++ )
		c = 0, dfs ( i, 1 );

	for ( lld i = 0; i < Q; i++ )
	{
		cin >> a >> b;
		if ( a <= 500 )
			cout << answer[a][b] << "\n";
		else
			cout << "0\n";
		fflush ( stdout );
	}
	return 0;
}

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