oj.uz

답안 #589749

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589749 2022-07-05T08:31:04 Z Drew_ Regions (IOI09_regions) C++17
1 / 100
 3279 ms 41116 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<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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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