oj.uz

Submission #116152

# Submission time Handle Problem Language Result Execution time Memory
116152 2019-06-11T03:14:44 Z luciocf Regions (IOI09_regions) C++14
55 / 100
 6027 ms 65900 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[maxn][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)
{
	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() > block)
			mp[i] = ++aux;

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

	dfs2(1, 0);

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


	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 9 ms 6144 KB Output is correct
2 Correct 8 ms 6272 KB Output is correct
3 Correct 9 ms 6272 KB Output is correct
4 Correct 11 ms 6144 KB Output is correct
5 Correct 13 ms 6144 KB Output is correct
6 Correct 14 ms 6272 KB Output is correct
7 Correct 41 ms 6272 KB Output is correct
8 Correct 20 ms 6272 KB Output is correct
9 Correct 72 ms 6656 KB Output is correct
10 Correct 95 ms 6784 KB Output is correct
11 Correct 142 ms 7040 KB Output is correct
12 Correct 117 ms 7424 KB Output is correct
13 Correct 174 ms 7544 KB Output is correct
14 Correct 342 ms 7932 KB Output is correct
15 Correct 307 ms 10232 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2195 ms 11896 KB Output isn't correct
2 Incorrect 2814 ms 10980 KB Output isn't correct
3 Incorrect 3315 ms 14548 KB Output isn't correct
4 Correct 251 ms 8060 KB Output is correct
5 Correct 393 ms 9464 KB Output is correct
6 Correct 1630 ms 9420 KB Output is correct
7 Correct 2183 ms 10552 KB Output is correct
8 Correct 1440 ms 15224 KB Output is correct
9 Correct 3033 ms 15912 KB Output is correct
10 Correct 5592 ms 20600 KB Output is correct
11 Correct 6027 ms 18464 KB Output is correct
12 Incorrect 1935 ms 36616 KB Output isn't correct
13 Incorrect 2812 ms 38048 KB Output isn't correct
14 Incorrect 4180 ms 42848 KB Output isn't correct
15 Incorrect 4824 ms 54912 KB Output isn't correct
16 Incorrect 4094 ms 65900 KB Output isn't correct
17 Incorrect 4410 ms 57464 KB Output isn't correct