//
// IOI09Regions.cpp
//
//
// Created by Matjaz Leonardis on 10/11/2023.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N,R,Q;
vector<vector<int> > s; // O(N)
vector<vector<int> > region_members; //O(N)
vector<int> H, S; // O(N)
vector<vector<int> > chain; // O(R * N)
vector<vector<int> > answer;
int time1 = 0;
vector<int> start; // O(N)
vector<int> end1; // O(N)
vector<bool> isBigRegion;
vector<int> bigRegionID;
int bigRegions = 0;
void compute_times(int x){
start[x] = time1;
time1++;
for (int i=0;i<s[x].size();i++){
compute_times(s[x][i]);
}
end1[x] = time1;
time1++;
}
void compute_bigregion_sums(int x) {
if (S[x] != -1){
chain[x] = chain[S[x]];
if (bigRegionID[H[S[x]]] != -1) chain[x][bigRegionID[H[S[x]]]]++;
}
if (bigRegionID[H[x]] != -1){
for (int i=0;i<bigRegions;i++) answer[i][bigRegionID[H[x]]] += chain[x][i];
}
for (int i=0;i<s[x].size();i++) compute_bigregion_sums(s[x][i]);
}
int main(){
cin >> N >> R >> Q;
H.assign(N, 0);
S.assign(N, 0);
region_members.assign(R, vector<int>());
for (int i=0;i<N;i++){
if (i == 0) cin >> H[i]; else
cin >> S[i] >> H[i];
S[i]--;
H[i]--;
region_members[H[i]].push_back(i);
}
s.assign(N, vector<int> ());
for (int i=1;i<N;i++) s[S[i]].push_back(i);
isBigRegion.assign(R, false);
bigRegionID.assign(R, -1);
for (int i=0;i<R;i++) isBigRegion[i] = region_members[i].size() > 500;
for (int i=0;i<R;i++) if (isBigRegion[i]){
bigRegionID[i] = bigRegions;
bigRegions++;
}
answer.assign(bigRegions, vector<int> (bigRegions));
chain.assign(N, vector<int> (bigRegions));
compute_bigregion_sums(0);
start.assign(N, -1);
end1.assign(N, -1);
compute_times(0);
vector<vector<int> > tmp(R, vector<int>()); // O(N)
for (int i=0;i<R;i++){
for (int j=0;j<region_members[i].size();j++) tmp[i].push_back(start[region_members[i][j]]);
sort(tmp[i].begin(), tmp[i].end());
}
for (int q=0;q<Q;q++){
int r1,r2;
cin >> r1 >> r2;
r1--;r2--;
int total = 0;
if (!isBigRegion[r1]){
for (int i=0;i<region_members[r1].size();i++){
int e1 = region_members[r1][i];
int strt = lower_bound(tmp[r2].begin(), tmp[r2].end(), start[e1]) - tmp[r2].begin();
int nd = lower_bound(tmp[r2].begin(), tmp[r2].end(), end1[e1]) - tmp[r2].begin();
total += nd - strt;
}
} else if (isBigRegion[r2]){
total = answer[bigRegionID[r1]][bigRegionID[r2]];
} else {
for (int i=0;i<region_members[r2].size();i++){
int e2 = region_members[r2][i];
total += chain[e2][bigRegionID[r1]];
}
}
cout << total << endl;
}
return 0;
}
Compilation message
regions.cpp: In function 'void compute_times(int)':
regions.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i=0;i<s[x].size();i++){
| ~^~~~~~~~~~~~
regions.cpp: In function 'void compute_bigregion_sums(int)':
regions.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i=0;i<s[x].size();i++) compute_bigregion_sums(s[x][i]);
| ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int j=0;j<region_members[i].size();j++) tmp[i].push_back(start[region_members[i][j]]);
| ~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int i=0;i<region_members[r1].size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for (int i=0;i<region_members[r2].size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
2 ms |
344 KB |
Output is correct |
| 5 |
Correct |
4 ms |
344 KB |
Output is correct |
| 6 |
Correct |
7 ms |
344 KB |
Output is correct |
| 7 |
Correct |
14 ms |
344 KB |
Output is correct |
| 8 |
Correct |
16 ms |
600 KB |
Output is correct |
| 9 |
Correct |
27 ms |
1112 KB |
Output is correct |
| 10 |
Correct |
50 ms |
1476 KB |
Output is correct |
| 11 |
Correct |
85 ms |
2032 KB |
Output is correct |
| 12 |
Correct |
95 ms |
2796 KB |
Output is correct |
| 13 |
Correct |
131 ms |
2648 KB |
Output is correct |
| 14 |
Correct |
221 ms |
3536 KB |
Output is correct |
| 15 |
Correct |
182 ms |
6592 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1577 ms |
13564 KB |
Output is correct |
| 2 |
Correct |
1805 ms |
12964 KB |
Output is correct |
| 3 |
Correct |
2372 ms |
15624 KB |
Output is correct |
| 4 |
Correct |
190 ms |
3828 KB |
Output is correct |
| 5 |
Correct |
255 ms |
5844 KB |
Output is correct |
| 6 |
Correct |
1134 ms |
6320 KB |
Output is correct |
| 7 |
Correct |
1352 ms |
8432 KB |
Output is correct |
| 8 |
Correct |
1085 ms |
14960 KB |
Output is correct |
| 9 |
Correct |
1816 ms |
18212 KB |
Output is correct |
| 10 |
Correct |
3705 ms |
24740 KB |
Output is correct |
| 11 |
Correct |
3997 ms |
21092 KB |
Output is correct |
| 12 |
Correct |
1151 ms |
27472 KB |
Output is correct |
| 13 |
Correct |
1572 ms |
27796 KB |
Output is correct |
| 14 |
Correct |
1722 ms |
41028 KB |
Output is correct |
| 15 |
Correct |
2518 ms |
33088 KB |
Output is correct |
| 16 |
Correct |
2201 ms |
38516 KB |
Output is correct |
| 17 |
Correct |
2136 ms |
52700 KB |
Output is correct |
