oj.uz

답안 #669999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
669999 2022-12-07T17:55:09 Z Iliya Regions (IOI09_regions) C++17
100 / 100
 5426 ms 84272 KB 
/*
 Lemme check my list of powers and weaknesses: 
 ability to do anything, but only whenever I want.
*/
 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int N = 2e5 + 10, R = 3e4, Q = 2e5 + 10, SQ = 499;
int n, r, q, Time, H[N], P[N], St[N], Ft[N], ID[R], cnt[N], Ans[SQ][R];
vector<int> Adj[N], Reg[R], Home[R];
 
void PreDFS(int v){
	St[v] = ++Time;
	Reg[H[v]].push_back(Time);
	for(int u : Adj[v])
		PreDFS(u);
	Ft[v] = Time;
}
 
void DFS(int v){
	if((int) Home[H[v]].size() >= SQ) cnt[ID[H[v]]]++;
	for(int u : Adj[v]){
		for(int i = 1; i < SQ; i++)
			Ans[i][H[u]] += cnt[i];
		DFS(u);
	}
	if((int) Home[H[v]].size() >= SQ) cnt[ID[H[v]]]--;
}
 
void solve(int r1, int r2){
	if((int) Home[r1].size() >= SQ) cout << Ans[ID[r1]][r2] << endl;
	else{
		int Res = 0;
		for(int x : Home[r1]){
			auto X1 = lower_bound(Reg[r2].begin(), Reg[r2].end(), St[x]);
			auto X2 = upper_bound(Reg[r2].begin(), Reg[r2].end(), Ft[x]);
			Res += X2 - X1;
		}
		cout << Res << endl;
	}
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
 
	cin >> n >> r >> q;
	for(int i = 1; i <= n; i++){
		if(i == 1){
			cin >> H[i];
			Home[H[i]].push_back(i);
		}
		else {
			cin >> P[i] >> H[i];
			Adj[P[i]].push_back(i);
			Home[H[i]].push_back(i);
		}
	}
	PreDFS(1);
	int ind = 0;
	for(int i = 1; i <= r; i++)
		if((int) Home[i].size() >= SQ)
			ID[i] = ++ind;
	DFS(1);
	while(q--){
		int r1, r2;
		cin >> r1 >> r2;
		solve(r1, r2);
	}
 
	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8528 KB Output is correct
2 Correct 4 ms 8528 KB Output is correct
3 Correct 6 ms 8528 KB Output is correct
4 Correct 8 ms 8528 KB Output is correct
5 Correct 10 ms 8656 KB Output is correct
6 Correct 23 ms 9040 KB Output is correct
7 Correct 25 ms 8940 KB Output is correct
8 Correct 20 ms 9040 KB Output is correct
9 Correct 46 ms 9808 KB Output is correct
10 Correct 50 ms 9980 KB Output is correct
11 Correct 139 ms 9964 KB Output is correct
12 Correct 161 ms 10968 KB Output is correct
13 Correct 200 ms 10320 KB Output is correct
14 Correct 323 ms 10676 KB Output is correct
15 Correct 261 ms 14572 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1975 ms 14320 KB Output is correct
2 Correct 2092 ms 12812 KB Output is correct
3 Correct 2774 ms 16936 KB Output is correct
4 Correct 339 ms 18248 KB Output is correct
5 Correct 473 ms 22484 KB Output is correct
6 Correct 991 ms 25472 KB Output is correct
7 Correct 1757 ms 32388 KB Output is correct
8 Correct 1534 ms 39512 KB Output is correct
9 Correct 2648 ms 48396 KB Output is correct
10 Correct 4534 ms 75044 KB Output is correct
11 Correct 5426 ms 67444 KB Output is correct
12 Correct 2183 ms 51264 KB Output is correct
13 Correct 2535 ms 51908 KB Output is correct
14 Correct 2925 ms 59328 KB Output is correct
15 Correct 3949 ms 75264 KB Output is correct
16 Correct 3512 ms 84272 KB Output is correct
17 Correct 3416 ms 72708 KB Output is correct