Submission #116157

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116157	2019-06-11T03:34:16 Z	luciocf	Regions (IOI09_regions)	C++14	55 / 100	7182 ms	131072 KB

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.0 / 15.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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)