#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, Bl = 400, n, r, q, c[N],idx = 0, tmin[N], tmout[N], id[N];
vector<int> heavy_p[25005], V[N];
vector<int> comp[N], x;
set<pii> occ[N];
void dfs(int u,int p) {
tmin[u] = ++t;
x[id[c[u]]]++;occ[c[u]].insert({tmin[u], occ[c[u]].size()});
for(int i = 0; i < V[u].size(); i++) {
dfs(V[u][i], u);
}
x[id[c[u]]]--;
for(int i = 0; i < x.size(); i++) {
heavy_p[c[u]][i] += x[i];
}
tmout[u] = t;
}
main(){
cin >> n >> r >> q;
cin >> c[1];
for(int i = 2; i <= n; i++) {
int p;
cin >> p >> c[i];
V[p].push_back(i);
}
for(int i = 1; i <= n; i++) {
comp[c[i]].push_back(i);
}
idx = 0;
for(int i = 1; i <= r; i++) {
if(comp[i].size() >= Bl) {
id[i] = ++idx;
}
}
for(int i = 1; i <= r; i++) {
heavy_p[i].resize(n/Bl + 2);
occ[i].insert({0, 0});
}
x.resize(n/Bl + 2);
dfs(1, 0);
for(int i = 1; i <= r; i++) {
occ[i].insert({n + 1, occ[i].size()});
}
while(q--) {
int r1,r2;
cin >> r1 >> r2;
if(comp[r1].size() >= Bl) {
cout << heavy_p[r2][id[r1]] << endl;
}
else {
int ans = 0;
for(int i = 0; i < comp[r1].size(); i++) {
int l = tmin[comp[r1][i]], r = tmout[comp[r1][i]];
ans += ((*occ[r2].upper_bound({r, n + 1})).s - 1 - (*--occ[r2].upper_bound({l - 1, n + 1})).s);
}
cout << ans << endl;
}
}
}
Compilation message
regions.cpp: In function 'void dfs(int, int)':
regions.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
regions.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
24 | main(){
| ^~~~
regions.cpp: In function 'int main()':
regions.cpp:37:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | if(comp[i].size() >= Bl) {
| ~~~~~~~~~~~~~~~^~~~~
regions.cpp:53:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
53 | if(comp[r1].size() >= Bl) {
| ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0; i < comp[r1].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19656 KB |
Output is correct |
2 |
Correct |
10 ms |
19656 KB |
Output is correct |
3 |
Correct |
10 ms |
19684 KB |
Output is correct |
4 |
Correct |
15 ms |
19656 KB |
Output is correct |
5 |
Correct |
15 ms |
19656 KB |
Output is correct |
6 |
Correct |
28 ms |
19784 KB |
Output is correct |
7 |
Correct |
31 ms |
19784 KB |
Output is correct |
8 |
Correct |
44 ms |
19912 KB |
Output is correct |
9 |
Correct |
57 ms |
20488 KB |
Output is correct |
10 |
Correct |
98 ms |
20676 KB |
Output is correct |
11 |
Correct |
117 ms |
21192 KB |
Output is correct |
12 |
Correct |
181 ms |
22000 KB |
Output is correct |
13 |
Correct |
227 ms |
21704 KB |
Output is correct |
14 |
Correct |
372 ms |
22424 KB |
Output is correct |
15 |
Correct |
397 ms |
26816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2415 ms |
28020 KB |
Output is correct |
2 |
Correct |
2787 ms |
26652 KB |
Output is correct |
3 |
Correct |
3844 ms |
31108 KB |
Output is correct |
4 |
Correct |
332 ms |
24144 KB |
Output is correct |
5 |
Correct |
438 ms |
27564 KB |
Output is correct |
6 |
Correct |
547 ms |
29180 KB |
Output is correct |
7 |
Correct |
1643 ms |
34488 KB |
Output is correct |
8 |
Correct |
1370 ms |
45632 KB |
Output is correct |
9 |
Correct |
2947 ms |
59096 KB |
Output is correct |
10 |
Correct |
3818 ms |
88000 KB |
Output is correct |
11 |
Correct |
7400 ms |
88492 KB |
Output is correct |
12 |
Correct |
2611 ms |
69740 KB |
Output is correct |
13 |
Correct |
3152 ms |
70404 KB |
Output is correct |
14 |
Correct |
3660 ms |
80100 KB |
Output is correct |
15 |
Correct |
5055 ms |
96308 KB |
Output is correct |
16 |
Correct |
4864 ms |
105772 KB |
Output is correct |
17 |
Correct |
4698 ms |
93340 KB |
Output is correct |