Submission #372769

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
372769	2021-03-01T15:01:38 Z	ngpin04	Regions (IOI09_regions)	C++14	95 / 100	4986 ms	131076 KB

regions

 #include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
const int S = sqrt(N);

map <int, int> ans[N];

vector <int> adj[N];
vector <int> id[N];

int grp[N];
int tin[N];
int tout[N];
int sum[N];
int n,m,q,cntdfs;

void dfs(int u = 1) {
	tin[u] = ++cntdfs;
	for (int v : adj[u]) 
		dfs(v);
	tout[u] = cntdfs;
}

void calc(int idgrp) {
	memset(sum, 0, sizeof(sum));

	for (int i : id[idgrp]) 
		sum[tin[i]]++, sum[tout[i] + 1]--;

	for (int i = 1; i <= n; i++)
		sum[i] += sum[i - 1];

	for (int i = 1; i <= n; i++) 
		if (grp[i] != idgrp) 
			ans[idgrp][grp[i]] += sum[tin[i]];

	memset(sum, 0, sizeof(sum));

	for (int i : id[idgrp]) 
		sum[tin[i]]++;

	for (int i = 1; i <= n; i++) 
		sum[i] += sum[i - 1];

	for (int i = 1; i <= n; i++)
		if (grp[i] != idgrp) 
			ans[grp[i]][idgrp] += sum[tout[i]] - sum[tin[i] - 1]; 
}

int solve(int u, int v) {
	int res = 0;
	vector <int> a;
	for (int i : id[v]) 
		a.push_back(tin[i]);
	
	for (int i : id[u]) 
		res += upper_bound(a.begin(), a.end(), tout[i]) - lower_bound(a.begin(), a.end(), tin[i]);

	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {	
		if (i > 1) {
			int p; cin >> p;
			adj[p].push_back(i);
		}
		cin >> grp[i];
		id[grp[i]].push_back(i);
	}
	dfs();

	for (int i = 1; i <= m; i++)
		sort(id[i].begin(), id[i].end(), [](int i, int j) {return tin[i] < tin[j];});

	for (int i = 1; i <= m; i++) 
		if (id[i].size() > S) 
			calc(i);

	for (int i = 1; i <= m; i++) if (id[i].size() > S) {
		for (int j = 1; j <= m; j++) if (id[j].size() > S) 
			ans[i][j] /= 2;
	}

	while (q--) {
		int u,v;
		cin >> u >> v;
		if (id[u].size() > S || id[v].size() > S) 
			cout << ans[u][v] << endl;
		else 
			cout << solve(u, v) << endl;
	}
	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	19180 KB	Output is correct
2	Correct	15 ms	19180 KB	Output is correct
3	Correct	15 ms	19180 KB	Output is correct
4	Correct	17 ms	19180 KB	Output is correct
5	Correct	20 ms	19180 KB	Output is correct
6	Correct	33 ms	19308 KB	Output is correct
7	Correct	45 ms	19180 KB	Output is correct
8	Correct	43 ms	19308 KB	Output is correct
9	Correct	64 ms	19564 KB	Output is correct
10	Correct	93 ms	19564 KB	Output is correct
11	Correct	162 ms	19820 KB	Output is correct
12	Correct	170 ms	20332 KB	Output is correct
13	Correct	217 ms	20076 KB	Output is correct
14	Correct	309 ms	20460 KB	Output is correct
15	Correct	359 ms	22380 KB	Output is correct

Subtask #2

80.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1555 ms	24172 KB	Output is correct
2	Correct	1588 ms	23276 KB	Output is correct
3	Correct	2539 ms	25580 KB	Output is correct
4	Correct	193 ms	20592 KB	Output is correct
5	Correct	420 ms	21740 KB	Output is correct
6	Correct	1322 ms	56796 KB	Output is correct
7	Correct	1907 ms	38252 KB	Output is correct
8	Correct	3911 ms	120652 KB	Output is correct
9	Correct	2918 ms	26988 KB	Output is correct
10	Runtime error	1929 ms	131076 KB	Execution killed with signal 9
11	Correct	4986 ms	26800 KB	Output is correct
12	Correct	1553 ms	31980 KB	Output is correct
13	Correct	2396 ms	31840 KB	Output is correct
14	Correct	3306 ms	64300 KB	Output is correct
15	Correct	3894 ms	36992 KB	Output is correct
16	Correct	3446 ms	40556 KB	Output is correct
17	Correct	4462 ms	72660 KB	Output is correct