oj.uz

답안 #116161

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116161 2019-06-11T03:46:59 Z luciocf Regions (IOI09_regions) C++17
100 / 100
 6388 ms 68716 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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