#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define endl printf("\n")
#define flush fflush(stdout)
#define pp pop_back
#define pr printf
#define sc scanf
#define debug(x) pr("%s , %i\n" , #x , x)
#define bg begin
#define arr(x) array<int , (x)>
typedef long long ll;
typedef pair<int , int> pii;
typedef long double ld;
const ll MOD = int(1e9) + 7;
const int root = 250;
const int inroot = 200000 / root + 1;
ll Sum(ll a , ll b){
ll res = a + b;
if(res > MOD) return (res - MOD);
if(res < 0) return (res + MOD);
return res;
}
ll Mul(ll a , ll b){
return (a * b) % MOD;
}
ll Pow(ll a , ll b){
ll res = 1;
while(b){
if((b & 1)) res = Mul(res , a);
a = Mul(a , a);
b >>= 1;
}
return res;
}
int n , r , q;
int wrg[200000];
vector<int> rgs[25000];
vector<int> g[200000];
int times[200000][2];
vector<int> tour[25000];
int mem[inroot][25000];
int rginx[200000];
int ps[200000];
int timer = -1;
void dfs0(int v = 0){
times[v][0] = ++timer;
tour[wrg[v]].pb(timer);
for(int u : g[v]) dfs0(u);
times[v][1] = timer;
}
void bfs0(int e){
fill(&ps[0] , &ps[n] , 0);
queue<arr(2)> q;
q.push({0 , -1});
while(!q.empty()){
auto d = q.front();
q.pop();
if(d[0] != 0){
ps[d[0]] = ps[d[1]];
if(wrg[d[1]] == e) ps[d[0]]++;
}
mem[rginx[e]][wrg[d[0]]] += ps[d[0]];
for(int u : g[d[0]]){
q.push({u , d[0]});
}
}
}
void init(){
int counter = 0;
for(int i = 0 ; i < r ; i++){
if(!rgs[i].empty() and (int)rgs[i].size() > root){
rginx[i] = counter;
bfs0(i);
counter++;
}
}
}
int f(int a , int c){
int res = 0;
for(int el : rgs[a]){
if(times[el][0] == times[el][1]) continue;
auto itr1 = ub(tour[c].bg() , tour[c].end() , times[el][0]);
auto itr2 = ub(tour[c].bg() , tour[c].end() , times[el][1]);
if(tour[c].empty() or itr2 == tour[c].bg()) continue;
itr2--;
res += int(itr2 - itr1 + 1);
}
return res;
}
int main(){
sc("%i%i%i" , &n , &r , &q);
int d;
sc("%i" , &d);
rgs[d - 1].pb(0);
wrg[0] = d - 1;
for(int i = 1 ; i < n ; i++){
int p;
sc("%i%i" , &p , &d);
rgs[d - 1].pb(i);
g[p - 1].pb(i);
wrg[i] = d - 1;
}
dfs0();
init();
for(int i = 0 ; i < q ; i++){
int a , b;
sc("%i%i" , &a , &b);
a-- , b--;
if(rgs[a].empty()) pr("0\n");
else if((int)rgs[a].size() <= root) pr("%i\n" , f(a , b));
else pr("%i\n" , mem[rginx[a]][b]);
flush;
}
/*
ZZZZZZZ A M M IIIIIII N N
Z A A M M M M I NN N
Z A A M M M M I N N N
Z AAAAAAA M M M I N N N
Z A A M M I N N N
Z A A M M I N NN
ZZZZZZZ A A M M IIIIIII N N TREE
*/
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:101:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | sc("%i%i%i" , &n , &r , &q);
| ^
regions.cpp:103:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | sc("%i" , &d);
| ^
regions.cpp:108:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | sc("%i%i" , &p , &d);
| ^
regions.cpp:118:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | sc("%i%i" , &a , &b);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9560 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9560 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9560 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9560 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9560 KB |
Output is correct |
| 6 |
Correct |
11 ms |
9560 KB |
Output is correct |
| 7 |
Correct |
15 ms |
9560 KB |
Output is correct |
| 8 |
Correct |
18 ms |
9560 KB |
Output is correct |
| 9 |
Correct |
30 ms |
10072 KB |
Output is correct |
| 10 |
Correct |
48 ms |
10072 KB |
Output is correct |
| 11 |
Correct |
79 ms |
10328 KB |
Output is correct |
| 12 |
Correct |
91 ms |
10556 KB |
Output is correct |
| 13 |
Correct |
108 ms |
10328 KB |
Output is correct |
| 14 |
Correct |
191 ms |
10832 KB |
Output is correct |
| 15 |
Correct |
198 ms |
12632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1272 ms |
17580 KB |
Output is correct |
| 2 |
Correct |
863 ms |
22888 KB |
Output is correct |
| 3 |
Correct |
2219 ms |
19500 KB |
Output is correct |
| 4 |
Correct |
164 ms |
11092 KB |
Output is correct |
| 5 |
Correct |
218 ms |
11992 KB |
Output is correct |
| 6 |
Correct |
308 ms |
20436 KB |
Output is correct |
| 7 |
Correct |
759 ms |
21324 KB |
Output is correct |
| 8 |
Correct |
690 ms |
28876 KB |
Output is correct |
| 9 |
Correct |
1360 ms |
29956 KB |
Output is correct |
| 10 |
Correct |
2069 ms |
33884 KB |
Output is correct |
| 11 |
Correct |
2703 ms |
58440 KB |
Output is correct |
| 12 |
Correct |
992 ms |
20756 KB |
Output is correct |
| 13 |
Correct |
1284 ms |
20788 KB |
Output is correct |
| 14 |
Correct |
1499 ms |
22952 KB |
Output is correct |
| 15 |
Correct |
2284 ms |
24220 KB |
Output is correct |
| 16 |
Correct |
2151 ms |
27348 KB |
Output is correct |
| 17 |
Correct |
2050 ms |
28916 KB |
Output is correct |
