Submission #378846

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378846	2021-03-17T06:02:28 Z	8e7	Regions (IOI09_regions)	C++14	100 / 100	7201 ms	32108 KB

regions

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define maxn 200005
#define maxc 25005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
vector<int> adj[maxn], pos[maxc], node[maxc];
int col[maxn], cnt[maxc], ind[1000], cor[maxc];

int ans[705][maxc], lef[maxn], rig[maxn];

int cur = 0, num = 0, c = 0;
void dfs(int n, int par) {
	lef[n] = c++;
	ans[cur][col[n]] += num;
	if (col[n] == ind[cur]) num++;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n);
		}
	}
	rig[n] = c;
	if (col[n] == ind[cur]) num--;
}
int main() {
	io
	int n, r, q;
	cin >> n >> r >> q;
	cin >> col[1];
	cnt[col[1]]++;
	node[col[1]].push_back(1);
	for (int i = 2;i <= n;i++) {
		int p;
		cin >> p >> col[i];
		adj[p].push_back(i);
		adj[i].push_back(p);
		node[col[i]].push_back(i);
		cnt[col[i]]++;
	}
	dfs(1, 0);
	int id = 0;
	for (int i = 1;i <= r;i++) {
		if (cnt[i] >= 300) {
			ind[id] = i;
			cor[i] = id;
			cur = id;
			c = 0;
			dfs(1, 0);
			id++;
		}
	}
	for (int i = 1;i <= n;i++) {
		pos[col[i]].push_back(lef[i]);
		//cout << col[i] << "  " << lef[i] << endl;
		//cout << lef[i] << " " << rig[i] << endl;
	}
	for (int i = 1;i <= r;i++) {
		sort(pos[i].begin(), pos[i].end());
		/*
		cout << i << ": " << endl;
		for (int v:pos[i]) cout << v<< " ";
		cout << endl;
		*/
	}
	for (int i = 0;i < q;i++) {
		int r1, r2;
		cin >> r1 >> r2;
		if (cnt[r1] >= 300) cout << ans[cor[r1]][r2] << endl;
		else {
			int ans = 0;
			for (int v:node[r1]) {
				int rn = upper_bound(pos[r2].begin(), pos[r2].end(), rig[v] - 1) - pos[r2].begin();
				int ln = lower_bound(pos[r2].begin(), pos[r2].end(), lef[v]) - pos[r2].begin();
				ans += rn - ln;
			}
			cout << ans << endl;
		}
	}
}
/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
 */

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6252 KB	Output is correct
2	Correct	4 ms	6252 KB	Output is correct
3	Correct	6 ms	6252 KB	Output is correct
4	Correct	8 ms	6252 KB	Output is correct
5	Correct	12 ms	6252 KB	Output is correct
6	Correct	20 ms	6380 KB	Output is correct
7	Correct	26 ms	6380 KB	Output is correct
8	Correct	29 ms	6380 KB	Output is correct
9	Correct	56 ms	6892 KB	Output is correct
10	Correct	99 ms	6892 KB	Output is correct
11	Correct	123 ms	7276 KB	Output is correct
12	Correct	148 ms	7660 KB	Output is correct
13	Correct	210 ms	7660 KB	Output is correct
14	Correct	334 ms	8172 KB	Output is correct
15	Correct	307 ms	11116 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2028 ms	11372 KB	Output is correct
2	Correct	2476 ms	10988 KB	Output is correct
3	Correct	3253 ms	13376 KB	Output is correct
4	Correct	271 ms	8264 KB	Output is correct
5	Correct	398 ms	9964 KB	Output is correct
6	Correct	564 ms	11500 KB	Output is correct
7	Correct	1143 ms	12908 KB	Output is correct
8	Correct	1263 ms	20716 KB	Output is correct
9	Correct	3033 ms	19832 KB	Output is correct
10	Correct	3597 ms	32108 KB	Output is correct
11	Correct	7201 ms	28524 KB	Output is correct
12	Correct	1731 ms	17320 KB	Output is correct
13	Correct	2248 ms	18412 KB	Output is correct
14	Correct	2867 ms	20224 KB	Output is correct
15	Correct	3867 ms	22796 KB	Output is correct
16	Correct	3395 ms	29932 KB	Output is correct
17	Correct	3366 ms	30104 KB	Output is correct