Submission #589665

#	Time	Username	Problem	Language	Result	Execution time	Memory
589665		Drew_	Regions (IOI09_regions)	C++17	0 / 100	4360 ms	34608 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<ii> item[MAXR];

int depth[MAXR];
static int cur_pos = 0;
inline int dfs_sz(int node)
{
	pos[node] = cur_pos++;
	sz[pos[node]] = 1;

	depth[region[node]]++;
	item[region[node]].pb({pos[node], depth[region[node]]});

	for (int to : adj[node])
		sz[pos[node]] += dfs_sz(to);
	depth[region[node]]--;
	return sz[pos[node]];
}

inline ll query1(const int &r1, const int &r2)
{
	ll res = 0;
	for (auto [node, dep] : item[r1])
	{
		int l = (int)(lower_bound(item[r2].begin(), item[r2].end(), mp(pos[node], inf)) - item[r2].begin());
		int r = (int)(lower_bound(item[r2].begin(), item[r2].end(), mp(pos[node] + sz[node] - 1, inf)) - item[r2].begin()); 
		res += (r-l);
	}
	return res;
}

inline ll query2(const int &r1, const int &r2)
{
	ll res = 0;
	for (auto [node, dep] : item[r2])
	{
		auto it = lower_bound(item[r1].begin(), item[r1].end(), mp(pos[node], inf));
		if (it == item[r1].begin())
			continue;
		res += prev(it) -> s2;
	}

	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);

	map<ii, ll> memo;
	for (int r1, r2; Q--;)
	{
		cin >> r1 >> r2;
		if (!memo.count({r1, r2}))
		{
			if (item[r1].size() < item[r2].size())
				memo[{r1, r2}] = query1(r1, r2);
			else memo[{r1, r2}] = query2(r1, r2);
		}

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

	return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85