//
// 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[r1][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 |
10 ms |
344 KB |
Output is correct |
| 7 |
Correct |
12 ms |
600 KB |
Output is correct |
| 8 |
Correct |
17 ms |
600 KB |
Output is correct |
| 9 |
Correct |
27 ms |
1112 KB |
Output is correct |
| 10 |
Correct |
45 ms |
1464 KB |
Output is correct |
| 11 |
Correct |
78 ms |
2016 KB |
Output is correct |
| 12 |
Correct |
100 ms |
2788 KB |
Output is correct |
| 13 |
Correct |
133 ms |
2648 KB |
Output is correct |
| 14 |
Correct |
209 ms |
3540 KB |
Output is correct |
| 15 |
Correct |
202 ms |
6596 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
53 ms |
27040 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
57 ms |
25760 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
69 ms |
31452 KB |
Execution killed with signal 11 |
| 4 |
Correct |
188 ms |
3832 KB |
Output is correct |
| 5 |
Correct |
248 ms |
5848 KB |
Output is correct |
| 6 |
Correct |
1071 ms |
6324 KB |
Output is correct |
| 7 |
Correct |
1344 ms |
8444 KB |
Output is correct |
| 8 |
Correct |
981 ms |
14964 KB |
Output is correct |
| 9 |
Correct |
1783 ms |
18208 KB |
Output is correct |
| 10 |
Correct |
3648 ms |
25016 KB |
Output is correct |
| 11 |
Correct |
3765 ms |
21084 KB |
Output is correct |
| 12 |
Correct |
1082 ms |
27468 KB |
Output is correct |
| 13 |
Correct |
1488 ms |
27672 KB |
Output is correct |
| 14 |
Runtime error |
197 ms |
82752 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
454 ms |
66628 KB |
Execution killed with signal 11 |
| 16 |
Correct |
2235 ms |
38504 KB |
Output is correct |
| 17 |
Runtime error |
194 ms |
106460 KB |
Execution killed with signal 11 |
