Submission #116161

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116161	2019-06-11T03:46:59 Z	luciocf	Regions (IOI09_regions)	C++17	100 / 100	6388 ms	68716 KB

regions

#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

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

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

ll ans[155][155], pre[maxr][155];

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() > block)
		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, int x)
{
	if (region[u] == r)
		++x;

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

		pre[region[v]][mp[r]] += 1ll*x;
		dfs3(v, u, r, x);
	}
}

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() > block)
			mp[i] = ++aux;

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

	dfs2(1, 0);

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

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

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	6272 KB	Output is correct
2	Correct	8 ms	6144 KB	Output is correct
3	Correct	12 ms	6272 KB	Output is correct
4	Correct	12 ms	6144 KB	Output is correct
5	Correct	15 ms	6144 KB	Output is correct
6	Correct	21 ms	6284 KB	Output is correct
7	Correct	43 ms	6272 KB	Output is correct
8	Correct	36 ms	6272 KB	Output is correct
9	Correct	37 ms	6656 KB	Output is correct
10	Correct	90 ms	6656 KB	Output is correct
11	Correct	134 ms	7160 KB	Output is correct
12	Correct	149 ms	7416 KB	Output is correct
13	Correct	214 ms	7544 KB	Output is correct
14	Correct	401 ms	7928 KB	Output is correct
15	Correct	411 ms	10232 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2360 ms	12200 KB	Output is correct
2	Correct	2840 ms	11072 KB	Output is correct
3	Correct	3019 ms	15156 KB	Output is correct
4	Correct	315 ms	8188 KB	Output is correct
5	Correct	381 ms	9464 KB	Output is correct
6	Correct	1635 ms	9464 KB	Output is correct
7	Correct	1901 ms	10488 KB	Output is correct
8	Correct	1485 ms	15136 KB	Output is correct
9	Correct	2834 ms	15992 KB	Output is correct
10	Correct	5214 ms	20584 KB	Output is correct
11	Correct	6388 ms	18440 KB	Output is correct
12	Correct	2037 ms	36432 KB	Output is correct
13	Correct	2562 ms	38240 KB	Output is correct
14	Correct	3869 ms	42892 KB	Output is correct
15	Correct	4389 ms	55880 KB	Output is correct
16	Correct	3978 ms	68716 KB	Output is correct
17	Correct	3726 ms	59984 KB	Output is correct