제출 #589749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589749		Drew_	Regions (IOI09_regions)	C++17	1 / 100	3279 ms	41116 KiB

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 / 15
• Subtask 2: 0 / 85