#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
struct FenwickTree {
vector<int> bit; // binary indexed tree
int n = MX;
int sum(int r) {
if(bit.empty()) bit.resize(n);
int ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
int sum(int l, int r) {
return sum(r) - sum(l - 1);
}
void add(int idx, int delta) {
if(bit.empty()) bit.resize(n);
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
};
const int B = 5;
int N, R, Q;
vector <int> g[MX], regionAll[MX], regionEl[MX];
int H[MX], st[MX], en[MX], timer=1;
int found[MX];
map <int, vector <int>> prep;
void Flat(int v, int p) {
st[v] = timer++;
if(!found[H[v]]) {
found[H[v]] = st[v];
regionEl[H[v]].push_back(v);
}
regionAll[H[v]].push_back(v);
for(auto to : g[v]) if(to!=p) {
Flat(to, v);
}
en[v] = timer-1;
if(found[H[v]]==st[v]) {
found[H[v]] = 0;
}
}
int main() {
cin >> N >> R >> Q;
cin >> H[1];
for(int i=2; i<=N; ++i) {
int p; cin >> p >> H[i];
g[p].push_back(i);
}
Flat(1, 1);
vector <int> bigs;
for(int i=1; i<=R; ++i) if(regionAll[i].size()>B) {
bigs.push_back(i);
}
int sz_big = bigs.size();
FenwickTree A;
for(int all=1; all<=R; ++all) {
for(auto it : regionAll[all]) {
A.add(st[it], 1);
}
for(auto b : bigs) {
if(prep[b].empty()) prep[b].resize(25001);
for(auto it : regionEl[b]) {
prep[b][all] += A.sum(st[it], en[it]);
}
}
for(auto it : regionAll[all]) {
A.add(st[it], -1);
}
}
map <int, FenwickTree> sb;
for(auto b : bigs) {
for(auto it : regionAll[b]) {
sb[b].add(st[it], 1);
}
}
while(Q--) {
int r1, r2;
cin >> r1 >> r2;
int ans = 0;
if(regionAll[r1].size()>B) {
ans = prep[r1][r2];
} else {
if(regionAll[r2].size()>B) {
for(auto it : regionEl[r1]) {
ans += sb[r2].sum(st[it], en[it]);
}
} else {
int p1 = 0, p2 = 0;
while(p1<regionEl[r1].size() && p2<regionAll[r2].size()) {
auto ok = [&] (int p1, int p2) {
return st[regionEl[r1][p1]]<=st[regionAll[r2][p2]] &&
en[regionEl[r1][p1]]>=en[regionAll[r2][p2]];
};
while(p2<regionAll[r2].size() && ok(p1, p2)) ++p2, ++ans;
while(p2<regionAll[r2].size() && st[regionAll[r2][p2]]<st[regionEl[r1][p1]]) ++p2;
if(p2==regionAll[r2].size()) continue;
while(p1<regionEl[r1].size() && en[regionEl[r1][p1]]<st[regionAll[r2][p2]]) ++p1;
}
}
}
cout << ans << endl;
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:94:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | while(p1<regionEl[r1].size() && p2<regionAll[r2].size()) {
| ~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:94:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | while(p1<regionEl[r1].size() && p2<regionAll[r2].size()) {
| ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:99:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | while(p2<regionAll[r2].size() && ok(p1, p2)) ++p2, ++ans;
| ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:100:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | while(p2<regionAll[r2].size() && st[regionAll[r2][p2]]<st[regionEl[r1][p1]]) ++p2;
| ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:101:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | if(p2==regionAll[r2].size()) continue;
| ~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:102:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | while(p1<regionEl[r1].size() && en[regionEl[r1][p1]]<st[regionAll[r2][p2]]) ++p1;
| ~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:59:6: warning: unused variable 'sz_big' [-Wunused-variable]
59 | int sz_big = bigs.size();
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
15976 KB |
Output isn't correct |
| 2 |
Incorrect |
8 ms |
15144 KB |
Output isn't correct |
| 3 |
Incorrect |
10 ms |
15176 KB |
Output isn't correct |
| 4 |
Incorrect |
16 ms |
24868 KB |
Output isn't correct |
| 5 |
Incorrect |
30 ms |
54088 KB |
Output isn't correct |
| 6 |
Incorrect |
29 ms |
43464 KB |
Output isn't correct |
| 7 |
Runtime error |
68 ms |
131076 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
67 ms |
131076 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
66 ms |
131076 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
259 ms |
131076 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
159 ms |
131076 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
115 ms |
131076 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
517 ms |
131076 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
243 ms |
131076 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
86 ms |
131076 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
115 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
206 ms |
131076 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
131 ms |
131076 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
3055 ms |
131076 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
83 ms |
131076 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
95 ms |
131076 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
123 ms |
131076 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
128 ms |
131076 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
172 ms |
131076 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
4141 ms |
131076 KB |
Execution killed with signal 9 |
| 11 |
Execution timed out |
8069 ms |
83136 KB |
Time limit exceeded |
| 12 |
Execution timed out |
8090 ms |
84276 KB |
Time limit exceeded |
| 13 |
Runtime error |
7505 ms |
131076 KB |
Execution killed with signal 9 |
| 14 |
Execution timed out |
8108 ms |
126364 KB |
Time limit exceeded |
| 15 |
Runtime error |
4622 ms |
131076 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
3557 ms |
131076 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
194 ms |
131076 KB |
Execution killed with signal 9 |
