oj.uz

답안 #372769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372769 2021-03-01T15:01:38 Z ngpin04 Regions (IOI09_regions) C++14
95 / 100
 4986 ms 131076 KB 
 #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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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