제출 #116157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116157		luciocf	Regions (IOI09_regions)	C++14	55 / 100	7182 ms	131072 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], pre[maxr][510];

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

map<int, int> mp;

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

	if (V[region[u]].size() > 500)
		ans[mp[region[u]]][mp[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;
}

void dfs3(int u, int p, int r)
{
	if (region[u] == r)
		++pre[region[u]][mp[r]];

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

		pre[region[v]][mp[r]] = pre[region[u]][mp[r]];
		dfs3(v, u, r);
	}
}

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 <= n; i++)
		V[region[i]].push_back(i);

	int aux = 0;
	for (int i = 1; i <= R; i++)
		if (V[i].size() > 500)
			mp[i] = ++aux;

	for (int i = 1; i <= R; i++)
	{
		if (V[i].size() > 500)
		{
			dfs(1, 0, i);
			dfs3(1, 0, i);
		}
	}

	dfs2(1, 0);

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

		if (V[r1].size() > 500 && V[r2].size() > 500)
		{
			cout << ans[mp[r1]][mp[r2]] << endl;
		}
		else if (V[r1].size() <= 500)
		{
			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;
		}
		else
		{
			cout << ans[r2][mp[r1]] << endl;
		}
	}
}

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