Submission #372768

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
372768	2021-03-01T14:55:17 Z	ngpin04	Regions (IOI09_regions)	C++14	60 / 100	5128 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) {
	for (int i = 1; i <= n; i++)
		sum[i] = 0;

	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]];

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

	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);

	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	15 ms	19180 KB	Output is correct
2	Correct	13 ms	19200 KB	Output is correct
3	Correct	16 ms	19180 KB	Output is correct
4	Correct	18 ms	19180 KB	Output is correct
5	Correct	21 ms	19180 KB	Output is correct
6	Correct	31 ms	19180 KB	Output is correct
7	Correct	39 ms	19180 KB	Output is correct
8	Correct	34 ms	19308 KB	Output is correct
9	Correct	60 ms	19564 KB	Output is correct
10	Correct	111 ms	19564 KB	Output is correct
11	Correct	140 ms	19820 KB	Output is correct
12	Correct	170 ms	20332 KB	Output is correct
13	Correct	236 ms	19948 KB	Output is correct
14	Correct	277 ms	20460 KB	Output is correct
15	Correct	306 ms	22380 KB	Output is correct

Subtask #2

45.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1465 ms	23728 KB	Output isn't correct
2	Incorrect	1575 ms	22636 KB	Output isn't correct
3	Incorrect	3296 ms	25212 KB	Output isn't correct
4	Correct	278 ms	20588 KB	Output is correct
5	Correct	449 ms	21740 KB	Output is correct
6	Incorrect	1423 ms	56116 KB	Output isn't correct
7	Correct	2146 ms	37732 KB	Output is correct
8	Correct	3872 ms	120416 KB	Output is correct
9	Correct	2772 ms	26988 KB	Output is correct
10	Runtime error	1935 ms	131076 KB	Execution killed with signal 9
11	Correct	5128 ms	26800 KB	Output is correct
12	Correct	1742 ms	31980 KB	Output is correct
13	Correct	2697 ms	31852 KB	Output is correct
14	Incorrect	3669 ms	64320 KB	Output isn't correct
15	Incorrect	4086 ms	36992 KB	Output isn't correct
16	Correct	3728 ms	40628 KB	Output is correct
17	Incorrect	4587 ms	72548 KB	Output isn't correct