Submission #589749

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
589749	2022-07-05T08:31:04 Z	Drew_	Regions (IOI09_regions)	C++17	1 / 100	3279 ms	41116 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]);
	}

	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] - 1) - 
					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

1.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7376 KB	Output is correct
2	Incorrect	4 ms	7376 KB	Output isn't correct
3	Incorrect	6 ms	7376 KB	Output isn't correct
4	Incorrect	8 ms	7420 KB	Output isn't correct
5	Incorrect	15 ms	7592 KB	Output isn't correct
6	Incorrect	25 ms	7520 KB	Output isn't correct
7	Incorrect	31 ms	7752 KB	Output isn't correct
8	Incorrect	40 ms	7632 KB	Output isn't correct
9	Incorrect	60 ms	8208 KB	Output isn't correct
10	Incorrect	89 ms	8700 KB	Output isn't correct
11	Incorrect	111 ms	9064 KB	Output isn't correct
12	Incorrect	124 ms	9792 KB	Output isn't correct
13	Incorrect	167 ms	9792 KB	Output isn't correct
14	Incorrect	213 ms	10420 KB	Output isn't correct
15	Incorrect	274 ms	12648 KB	Output isn't correct

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1029 ms	15132 KB	Output isn't correct
2	Incorrect	846 ms	14304 KB	Output isn't correct
3	Incorrect	1884 ms	18880 KB	Output isn't correct
4	Incorrect	240 ms	11452 KB	Output isn't correct
5	Incorrect	414 ms	13364 KB	Output isn't correct
6	Incorrect	538 ms	13556 KB	Output isn't correct
7	Incorrect	872 ms	14268 KB	Output isn't correct
8	Incorrect	1100 ms	21480 KB	Output isn't correct
9	Incorrect	1706 ms	29212 KB	Output isn't correct
10	Incorrect	3085 ms	34528 KB	Output isn't correct
11	Incorrect	3279 ms	34136 KB	Output isn't correct
12	Incorrect	1223 ms	27612 KB	Output isn't correct
13	Incorrect	1662 ms	29684 KB	Output isn't correct
14	Incorrect	1753 ms	31748 KB	Output isn't correct
15	Incorrect	2775 ms	37944 KB	Output isn't correct
16	Incorrect	3038 ms	41116 KB	Output isn't correct
17	Incorrect	2971 ms	40140 KB	Output isn't correct