Submission #378843

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378843	2021-03-17T05:59:50 Z	8e7	Regions (IOI09_regions)	C++14	100 / 100	6121 ms	30060 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;
const int siz = 128;
vector<int> adj[maxn], pos[maxc], node[maxc];
int col[maxn], cnt[maxc], ind[1000], cor[maxc];

int ans[505][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] >= 500) {
			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] >= 500) 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();
				//cout << v << ' ' << " " << rn << " " << ln << endl;
				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	5 ms	6252 KB	Output is correct
3	Correct	8 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	24 ms	6380 KB	Output is correct
7	Correct	36 ms	6380 KB	Output is correct
8	Correct	37 ms	6380 KB	Output is correct
9	Correct	55 ms	6932 KB	Output is correct
10	Correct	87 ms	6892 KB	Output is correct
11	Correct	164 ms	7276 KB	Output is correct
12	Correct	178 ms	7660 KB	Output is correct
13	Correct	224 ms	7800 KB	Output is correct
14	Correct	366 ms	8172 KB	Output is correct
15	Correct	313 ms	11116 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2196 ms	11380 KB	Output is correct
2	Correct	2739 ms	10928 KB	Output is correct
3	Correct	3291 ms	13380 KB	Output is correct
4	Correct	301 ms	8320 KB	Output is correct
5	Correct	415 ms	9964 KB	Output is correct
6	Correct	1553 ms	10220 KB	Output is correct
7	Correct	2145 ms	10860 KB	Output is correct
8	Correct	1625 ms	16492 KB	Output is correct
9	Correct	2709 ms	16620 KB	Output is correct
10	Correct	5479 ms	22252 KB	Output is correct
11	Correct	6121 ms	18796 KB	Output is correct
12	Correct	1984 ms	17324 KB	Output is correct
13	Correct	2795 ms	18336 KB	Output is correct
14	Correct	3259 ms	20284 KB	Output is correct
15	Correct	4130 ms	22784 KB	Output is correct
16	Correct	3974 ms	29932 KB	Output is correct
17	Correct	3576 ms	30060 KB	Output is correct