oj.uz

답안 #116144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116144 2019-06-10T21:08:43 Z luciocf Regions (IOI09_regions) C++14
80 / 100
 8000 ms 26528 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 6272 KB Output is correct
2 Correct 7 ms 6144 KB Output is correct
3 Correct 8 ms 6272 KB Output is correct
4 Correct 11 ms 6272 KB Output is correct
5 Correct 12 ms 6400 KB Output is correct
6 Correct 16 ms 7168 KB Output is correct
7 Correct 36 ms 6784 KB Output is correct
8 Correct 37 ms 7040 KB Output is correct
9 Correct 53 ms 8040 KB Output is correct
10 Correct 228 ms 8236 KB Output is correct
11 Correct 194 ms 7928 KB Output is correct
12 Correct 395 ms 9088 KB Output is correct
13 Correct 405 ms 8440 KB Output is correct
14 Correct 324 ms 8056 KB Output is correct
15 Correct 252 ms 11696 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1174 ms 10892 KB Output is correct
2 Correct 1115 ms 10232 KB Output is correct
3 Correct 1578 ms 13264 KB Output is correct
4 Correct 345 ms 8056 KB Output is correct
5 Correct 448 ms 9464 KB Output is correct
6 Correct 1690 ms 9336 KB Output is correct
7 Correct 1996 ms 10488 KB Output is correct
8 Correct 1202 ms 15096 KB Output is correct
9 Correct 2962 ms 16044 KB Output is correct
10 Correct 5108 ms 20628 KB Output is correct
11 Correct 5930 ms 18424 KB Output is correct
12 Correct 7276 ms 16888 KB Output is correct
13 Correct 7740 ms 17648 KB Output is correct
14 Execution timed out 8042 ms 18060 KB Time limit exceeded
15 Execution timed out 8087 ms 21240 KB Time limit exceeded
16 Execution timed out 8077 ms 26528 KB Time limit exceeded
17 Execution timed out 8005 ms 25412 KB Time limit exceeded