Submission #116144

#	Time	Username	Problem	Language	Result	Execution time	Memory
116144		luciocf	Regions (IOI09_regions)	C++14	80 / 100	8087 ms	26528 KiB

regions

#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

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

int st[maxn], en[maxn], tt;

ll ans[510][510];

vector<int> grafo[maxn], pos[maxr], V[maxr];

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

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

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

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

void dfs2(int u, int p)
{
	st[u] = ++tt;
	pos[region[u]].push_back(tt);

	for (auto v: grafo[u])
		if (v != p)
			dfs2(v, u);

	en[u] = tt;
}

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);
	}

	if (R <= 500)
	{
		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;
		}
	}
	else
	{
		for (int i = 1; i <= n; i++)
			V[region[i]].push_back(i);

		dfs2(1, 0);

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

			int Ans = 0;

			for (auto ind: V[r1])
			{
				int l = st[ind], r = en[ind];

				vector<int>::iterator it1 = lower_bound(pos[r2].begin(), pos[r2].end(), l);
				vector<int>::iterator it2 = upper_bound(pos[r2].begin(), pos[r2].end(), r);

				if (it1 == pos[r2].end()) continue;
				if (it2 == pos[r2].begin()) continue;

				--it2;

				int pos1 = (int)(it1-pos[r2].begin()), pos2 = (int)(it2-pos[r2].begin());

				if (pos[r2][pos1] > r || pos[r2][pos2] < l) continue;

				Ans += (pos2-pos1+1);
			}

			cout << Ans << endl;
		}
	}
}

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