#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, char separator = ' ', char finish = '\n'){
for(auto item: container) cout << item << separator;
cout << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#pragma GCC optimize("O3,avx2")
const long N = 2e5 + 69, R = 25000;
long n, rr, q;
vector<long> graph[N];
vector<long> area[R], vaix[R], king[R];
long l[N], r[N];
long dfs_cnt = 0;
void dfs(long u){
l[u] = r[u] = ++dfs_cnt;
for(long v: graph[u]){
dfs(v);
maximize(r[u], r[v]);
}
}
ll calc1(long u, long v){
ll ans = 0;
for(long i: vaix[u]) {
ans += upper_bound(ALL(area[v]), r[i]) - lower_bound(ALL(area[v]), l[i]);
}
return ans;
}
bool compare(long a, long b){return l[a] < l[b];}
ll calc2(long u, long v){
ll ans = 0;
if (area[v].size() * 3 <= area[u].size()){
long x= 0, y = 0;
for(long i: vaix[v]){
while(x < king[u].size() && king[u][x] < l[i]) x++;
ans += (int)king[u].size() - x;
while(y < area[u].size() && area[u][y] <= l[i]) y++;
ans -= (int)area[u].size() - y;
}
return ans;
}
for(long i: vaix[v]){
long x = lower_bound(ALL(king[u]), l[i]) - king[u].begin();
ans += king[u].size() - x;
long y = upper_bound(ALL(area[u]), l[i]) - area[u].begin();
ans -= area[u].size() - y;
}
return ans;
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> rr >> q;
long h; cin >> h; vaix[h].push_back(1);
for(long i = 2; i<=n; ++i){
long p, h; cin >> p >> h;
graph[p].push_back(i);
vaix[h].push_back(i);
}
dfs(1);
for(long i= 1; i<=rr; ++i){
for(long v: vaix[i]) {
area[i].push_back(l[v]);
king[i].push_back(r[v]);
}
sort(ALL(vaix[i]), compare);
sort(ALL(area[i]));
sort(ALL(king[i]));
}
map<pair<long, long>, long> mp;
while(q--){
long r1, r2; cin >> r1 >> r2;
if (mp.count({r1, r2})) {
cout << mp[{r1, r2}] << endl;
continue;
}
if (area[r1].size() <= area[r2].size()) {
cout << (mp[{r1, r2}] = calc1(r1, r2)) << endl;
}
else{
cout << (mp[{r1, r2}] = calc2(r1, r2)) << endl;
}
}
return 0;
}
Compilation message
regions.cpp:47:31: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
47 | #pragma GCC optimize("O3,avx2")
| ^
regions.cpp:57:16: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
57 | void dfs(long u){
| ^
regions.cpp:65:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
65 | ll calc1(long u, long v){
| ^
regions.cpp:73:28: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
73 | bool compare(long a, long b){return l[a] < l[b];}
| ^
regions.cpp:75:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
75 | ll calc2(long u, long v){
| ^
regions.cpp: In function 'll calc2(long int, long int)':
regions.cpp:80:21: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | while(x < king[u].size() && king[u][x] < l[i]) x++;
| ~~^~~~~~~~~~~~~~~~
regions.cpp:82:21: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | while(y < area[u].size() && area[u][y] <= l[i]) y++;
| ~~^~~~~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:96:14: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
96 | int main(void){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9884 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9884 KB |
Output is correct |
| 4 |
Correct |
4 ms |
10152 KB |
Output is correct |
| 5 |
Correct |
6 ms |
10180 KB |
Output is correct |
| 6 |
Correct |
11 ms |
10732 KB |
Output is correct |
| 7 |
Correct |
17 ms |
10836 KB |
Output is correct |
| 8 |
Correct |
22 ms |
10632 KB |
Output is correct |
| 9 |
Correct |
26 ms |
12016 KB |
Output is correct |
| 10 |
Correct |
55 ms |
11760 KB |
Output is correct |
| 11 |
Correct |
85 ms |
12500 KB |
Output is correct |
| 12 |
Correct |
104 ms |
13156 KB |
Output is correct |
| 13 |
Correct |
114 ms |
12828 KB |
Output is correct |
| 14 |
Correct |
192 ms |
13708 KB |
Output is correct |
| 15 |
Correct |
212 ms |
15424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
798 ms |
17636 KB |
Output is correct |
| 2 |
Correct |
949 ms |
16952 KB |
Output is correct |
| 3 |
Correct |
1509 ms |
21092 KB |
Output is correct |
| 4 |
Correct |
195 ms |
14548 KB |
Output is correct |
| 5 |
Correct |
245 ms |
15672 KB |
Output is correct |
| 6 |
Correct |
364 ms |
16432 KB |
Output is correct |
| 7 |
Correct |
519 ms |
16784 KB |
Output is correct |
| 8 |
Correct |
715 ms |
23304 KB |
Output is correct |
| 9 |
Correct |
1453 ms |
30692 KB |
Output is correct |
| 10 |
Correct |
3138 ms |
35652 KB |
Output is correct |
| 11 |
Correct |
3712 ms |
34504 KB |
Output is correct |
| 12 |
Correct |
1370 ms |
28400 KB |
Output is correct |
| 13 |
Correct |
1876 ms |
29952 KB |
Output is correct |
| 14 |
Correct |
2054 ms |
31788 KB |
Output is correct |
| 15 |
Correct |
2888 ms |
37172 KB |
Output is correct |
| 16 |
Correct |
2597 ms |
40508 KB |
Output is correct |
| 17 |
Correct |
2513 ms |
40276 KB |
Output is correct |
