#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pp pop_back
#define pr printf
#define sc scanf
#define endl pr("\n")
#define debug(x) pr("%s , %i\n" , #x , x)
#define bg begin
#define arr(x) array<int , (x)>
#define flush fflush(stdout)
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[25000];
int ps[200000];
int timer = -1;
void dfs(int v = 0){
times[v][0] = ++timer;
tour[wrg[v]].pb(timer);
for(int u : g[v]) dfs(u);
times[v][1] = timer;
}
void bfs(int e){
queue<arr(3)> que;
que.push({0 , -1 , 0});
while(!que.empty()){
auto d = que.front();
que.pop();
if(d[0] != 0 and wrg[d[1]] == e) d[2]++;
mem[rginx[e]][wrg[d[0]]] += d[2];
for(int u : g[d[0]]) que.push({u , d[0] , d[2]});
}
}
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++;
bfs(i);
}
}
}
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;
}
dfs();
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:94:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | sc("%i%i%i" , &n , &r , &q);
| ^
regions.cpp:96:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | sc("%i" , &d);
| ^
regions.cpp:101:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | sc("%i%i" , &p , &d);
| ^
regions.cpp:111:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | sc("%i%i" , &a , &b);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8792 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8792 KB |
Output is correct |
| 5 |
Correct |
6 ms |
8792 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9048 KB |
Output is correct |
| 7 |
Correct |
14 ms |
9048 KB |
Output is correct |
| 8 |
Correct |
16 ms |
9048 KB |
Output is correct |
| 9 |
Correct |
23 ms |
9304 KB |
Output is correct |
| 10 |
Correct |
44 ms |
9304 KB |
Output is correct |
| 11 |
Correct |
72 ms |
9560 KB |
Output is correct |
| 12 |
Correct |
75 ms |
10072 KB |
Output is correct |
| 13 |
Correct |
99 ms |
9816 KB |
Output is correct |
| 14 |
Correct |
178 ms |
10240 KB |
Output is correct |
| 15 |
Correct |
202 ms |
12200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1285 ms |
16720 KB |
Output is correct |
| 2 |
Correct |
814 ms |
21820 KB |
Output is correct |
| 3 |
Correct |
2103 ms |
16044 KB |
Output is correct |
| 4 |
Correct |
154 ms |
10328 KB |
Output is correct |
| 5 |
Correct |
246 ms |
11296 KB |
Output is correct |
| 6 |
Correct |
330 ms |
19364 KB |
Output is correct |
| 7 |
Correct |
672 ms |
18456 KB |
Output is correct |
| 8 |
Correct |
696 ms |
28076 KB |
Output is correct |
| 9 |
Correct |
1387 ms |
29224 KB |
Output is correct |
| 10 |
Correct |
2044 ms |
32768 KB |
Output is correct |
| 11 |
Correct |
2730 ms |
57628 KB |
Output is correct |
| 12 |
Correct |
930 ms |
19892 KB |
Output is correct |
| 13 |
Correct |
1268 ms |
20200 KB |
Output is correct |
| 14 |
Correct |
1485 ms |
22096 KB |
Output is correct |
| 15 |
Correct |
2247 ms |
23364 KB |
Output is correct |
| 16 |
Correct |
2029 ms |
26316 KB |
Output is correct |
| 17 |
Correct |
2019 ms |
27896 KB |
Output is correct |
