oj.uz

답안 #116157

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116157 2019-06-11T03:34:16 Z luciocf Regions (IOI09_regions) C++14
55 / 100
 7182 ms 131072 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], 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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 6144 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 6144 KB Output is correct
5 Correct 9 ms 6144 KB Output is correct
6 Correct 28 ms 6272 KB Output is correct
7 Correct 34 ms 6272 KB Output is correct
8 Correct 33 ms 6272 KB Output is correct
9 Correct 65 ms 6656 KB Output is correct
10 Correct 119 ms 6656 KB Output is correct
11 Correct 180 ms 7040 KB Output is correct
12 Correct 139 ms 7416 KB Output is correct
13 Correct 184 ms 7680 KB Output is correct
14 Correct 366 ms 7928 KB Output is correct
15 Correct 361 ms 10232 KB Output is correct

Subtask #2
40.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1956 ms 12480 KB Output isn't correct
2 Incorrect 2526 ms 11676 KB Output isn't correct
3 Incorrect 3219 ms 15364 KB Output isn't correct
4 Correct 266 ms 8056 KB Output is correct
5 Correct 295 ms 9464 KB Output is correct
6 Correct 1666 ms 9380 KB Output is correct
7 Correct 1917 ms 10560 KB Output is correct
8 Correct 1512 ms 15064 KB Output is correct
9 Correct 2822 ms 15960 KB Output is correct
10 Correct 4892 ms 20604 KB Output is correct
11 Correct 7182 ms 18392 KB Output is correct
12 Runtime error 512 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 412 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 1868 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 325 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 246 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 995 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)