oj.uz

Submission #589665

# Submission time Handle Problem Language Result Execution time Memory
589665 2022-07-05T05:51:36 Z Drew_ Regions (IOI09_regions) C++17
0 / 100
 4360 ms 34608 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5584 KB Output isn't correct
2 Incorrect 3 ms 5584 KB Output isn't correct
3 Incorrect 4 ms 5584 KB Output isn't correct
4 Incorrect 9 ms 5648 KB Output isn't correct
5 Incorrect 13 ms 5584 KB Output isn't correct
6 Incorrect 26 ms 5840 KB Output isn't correct
7 Incorrect 37 ms 5780 KB Output isn't correct
8 Incorrect 33 ms 5876 KB Output isn't correct
9 Incorrect 26 ms 6328 KB Output isn't correct
10 Incorrect 98 ms 6504 KB Output isn't correct
11 Incorrect 124 ms 6992 KB Output isn't correct
12 Incorrect 123 ms 7532 KB Output isn't correct
13 Incorrect 226 ms 7300 KB Output isn't correct
14 Incorrect 268 ms 8184 KB Output isn't correct
15 Incorrect 302 ms 10076 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1200 ms 11824 KB Output isn't correct
2 Incorrect 1424 ms 10708 KB Output isn't correct
3 Incorrect 1853 ms 15528 KB Output isn't correct
4 Incorrect 302 ms 8716 KB Output isn't correct
5 Incorrect 409 ms 10552 KB Output isn't correct
6 Incorrect 606 ms 10392 KB Output isn't correct
7 Incorrect 916 ms 10568 KB Output isn't correct
8 Incorrect 1157 ms 17336 KB Output isn't correct
9 Incorrect 2080 ms 22764 KB Output isn't correct
10 Incorrect 3713 ms 28144 KB Output isn't correct
11 Incorrect 4360 ms 26064 KB Output isn't correct
12 Incorrect 1114 ms 21108 KB Output isn't correct
13 Incorrect 1839 ms 23120 KB Output isn't correct
14 Incorrect 2136 ms 24320 KB Output isn't correct
15 Incorrect 3589 ms 30300 KB Output isn't correct
16 Incorrect 3155 ms 34608 KB Output isn't correct
17 Incorrect 3484 ms 33580 KB Output isn't correct