oj.uz

Submission #372770

# Submission time Handle Problem Language Result Execution time Memory
372770 2021-03-01T15:10:21 Z ngpin04 Regions (IOI09_regions) C++14
100 / 100
 5022 ms 64484 KB 
 #include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
const int S = 700;

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 13 ms 19180 KB Output is correct
3 Correct 16 ms 19180 KB Output is correct
4 Correct 17 ms 19180 KB Output is correct
5 Correct 21 ms 19180 KB Output is correct
6 Correct 34 ms 19180 KB Output is correct
7 Correct 53 ms 19180 KB Output is correct
8 Correct 56 ms 19328 KB Output is correct
9 Correct 67 ms 19564 KB Output is correct
10 Correct 107 ms 19692 KB Output is correct
11 Correct 130 ms 19820 KB Output is correct
12 Correct 161 ms 20332 KB Output is correct
13 Correct 189 ms 19948 KB Output is correct
14 Correct 319 ms 20460 KB Output is correct
15 Correct 291 ms 22380 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1606 ms 23916 KB Output is correct
2 Correct 1597 ms 23148 KB Output is correct
3 Correct 3093 ms 25580 KB Output is correct
4 Correct 321 ms 20588 KB Output is correct
5 Correct 422 ms 21772 KB Output is correct
6 Correct 1687 ms 21612 KB Output is correct
7 Correct 1949 ms 22508 KB Output is correct
8 Correct 1413 ms 26348 KB Output is correct
9 Correct 2445 ms 26988 KB Output is correct
10 Correct 5022 ms 30724 KB Output is correct
11 Correct 4725 ms 26800 KB Output is correct
12 Correct 1647 ms 31980 KB Output is correct
13 Correct 2507 ms 31852 KB Output is correct
14 Correct 3092 ms 56336 KB Output is correct
15 Correct 3973 ms 36992 KB Output is correct
16 Correct 3797 ms 40684 KB Output is correct
17 Correct 4447 ms 64484 KB Output is correct