Submission #116142

#	Time	Username	Problem	Language	Result	Execution time	Memory
116142		luciocf	Regions (IOI09_regions)	C++14	30 / 100	1254 ms	53624 KiB

regions

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;
const int maxr = 510;

typedef long long ll;

int n, R, q;
int region[maxn];

ll ans[maxr][maxr];

vector<int> grafo[maxn];

int dfs(int u, int p, int r)
{
	int qtd = 0;
	if (region[u] == r)
		qtd = 1;

	for (auto v: grafo[u])
	{
		if (v == p) continue;

		qtd += dfs(v, u, r);
	}

	ans[region[u]][r] += 1ll*qtd;
	return qtd;
}

int main(void)
{
	cin >> n >> R >> q;

	cin >> region[1];
	for (int i = 2; i <= n; i++)
	{
		int p;
		cin >> p >> region[i];

		grafo[i].push_back(p); grafo[p].push_back(i);
	}

	for (int i = 1; i <= R; i++)
		dfs(1, 0, i);

	for (int i = 1; i <= q; i++)
	{
		int r1, r2;
		cin >> r1 >> r2;

		cout << ans[r1][r2] << endl;
	}
}

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