oj.uz

답안 #372768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372768 2021-03-01T14:55:17 Z ngpin04 Regions (IOI09_regions) C++14
60 / 100
 5128 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) {
	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

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

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