Submission #589763

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
589763	2022-07-05T08:51:45 Z	Drew_	Regions (IOI09_regions)	C++17	100 / 100	3685 ms	41304 KB

regions

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 fisrt
#define s2 second

using ii = pair<int, int>;
using ll = long long;

const int MAXN = 2e5 + 69;
const int MAXR = 25069;
const int inf = 1e9 + 69;

int N, R, Q;
int region[MAXN], pos[MAXN], sz[MAXN];
vector<int> adj[MAXN];
vector<int> people[MAXR];

inline int dfs_sz(int node)
{
	static int cur_pos = 0;

	pos[node] = cur_pos++; sz[node] = 1;
	people[region[node]].pb(node);
	for (int to : adj[node])
		sz[node] += dfs_sz(to);
	return sz[node];
}

namespace Q1 // light parent, heavy child
{
	vector<int> item[MAXR];
	void build()
	{
		for (int i = 1; i <= N; ++i)
			item[region[i]].pb(pos[i]);
		for (int i = 1; i <= R; ++i)
			sort(item[i].begin(), item[i].end());
	}

	inline ll query(int r1, int r2)
	{
		ll res = 0;
		for (int node : people[r1])
		{
			res += (lower_bound(item[r2].begin(), item[r2].end(), pos[node] + sz[node]) - 
					lower_bound(item[r2].begin(), item[r2].end(), pos[node]));
		}
		return res;
	}
}

namespace Q2 // heavy parent, light child
{
	vector<int> item[MAXR], pfx[MAXR];
	void build()
	{
		for (int i = 1; i <= R; ++i)
		{
			vector<ii> vec;			
			for (int node : people[i])
			{
				vec.pb({pos[node], 1});
				vec.pb({pos[node] + sz[node], -1});
			}
			sort(vec.begin(), vec.end());

			item[i].pb(-1); pfx[i].pb(0);
			for (auto &[a, b] : vec)
			{
				item[i].pb(a);
				pfx[i].pb(pfx[i].back() + b);
			}
		}
	}

	inline ll query(int r1, int r2)
	{
		ll res = 0;
		for (int node : people[r2])
		{
			int id = (int)(upper_bound(item[r1].begin(), item[r1].end(), pos[node]) - item[r1].begin()) - 1;
			res += pfx[r1][id];
		}
		return res;
	}	
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> R >> Q;
	for (int i = 1, p; i <= N; ++i)
	{
		if (i > 1)
		{
			cin >> p;
			adj[p].pb(i);
		}
		cin >> region[i];
	}

	dfs_sz(1);
	Q1::build();
	Q2::build();

	map<ii, ll> memo;
	for (int r1, r2; Q--;)
	{
		cin >> r1 >> r2;
		if (!memo.count({r1, r2}))
		{
			if (people[r1].size() <= people[r2].size())
				memo[{r1, r2}] = Q1::query(r1, r2);
			else memo[{r1, r2}] = Q2::query(r1, r2);
		}

		cout << memo[{r1, r2}] << endl;
	}

	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7376 KB	Output is correct
2	Correct	4 ms	7376 KB	Output is correct
3	Correct	6 ms	7376 KB	Output is correct
4	Correct	8 ms	7376 KB	Output is correct
5	Correct	10 ms	7376 KB	Output is correct
6	Correct	13 ms	7568 KB	Output is correct
7	Correct	37 ms	7608 KB	Output is correct
8	Correct	21 ms	7632 KB	Output is correct
9	Correct	68 ms	8340 KB	Output is correct
10	Correct	91 ms	8484 KB	Output is correct
11	Correct	123 ms	8980 KB	Output is correct
12	Correct	152 ms	9804 KB	Output is correct
13	Correct	166 ms	9884 KB	Output is correct
14	Correct	246 ms	10416 KB	Output is correct
15	Correct	234 ms	12712 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1274 ms	14956 KB	Output is correct
2	Correct	1109 ms	14192 KB	Output is correct
3	Correct	2177 ms	18872 KB	Output is correct
4	Correct	358 ms	11484 KB	Output is correct
5	Correct	246 ms	13364 KB	Output is correct
6	Correct	610 ms	13432 KB	Output is correct
7	Correct	526 ms	14384 KB	Output is correct
8	Correct	1155 ms	21448 KB	Output is correct
9	Correct	2270 ms	29164 KB	Output is correct
10	Correct	3329 ms	34640 KB	Output is correct
11	Correct	3685 ms	34216 KB	Output is correct
12	Correct	1416 ms	27584 KB	Output is correct
13	Correct	1812 ms	29624 KB	Output is correct
14	Correct	2454 ms	31752 KB	Output is correct
15	Correct	3316 ms	37924 KB	Output is correct
16	Correct	2850 ms	41304 KB	Output is correct
17	Correct	3158 ms	40232 KB	Output is correct