#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][inroot];
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(2)> que;
que.push({0 , -1});
while(!que.empty()){
auto d = que.front();
que.pop();
if(d[0] != 0){
ps[d[0]][rginx[e]] = ps[d[1]][rginx[e]];
if(wrg[d[1]] == e) ps[d[0]][rginx[e]]++;
}
mem[rginx[e]][wrg[d[0]]] += ps[d[0]][rginx[e]];
for(int u : g[d[0]]) que.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++;
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:97:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | sc("%i%i%i" , &n , &r , &q);
| ^
regions.cpp:99:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | sc("%i" , &d);
| ^
regions.cpp:104:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | sc("%i%i" , &p , &d);
| ^
regions.cpp:114:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | sc("%i%i" , &a , &b);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9304 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9304 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9304 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9304 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9304 KB |
Output is correct |
| 6 |
Correct |
11 ms |
9304 KB |
Output is correct |
| 7 |
Correct |
16 ms |
9304 KB |
Output is correct |
| 8 |
Correct |
18 ms |
9304 KB |
Output is correct |
| 9 |
Correct |
26 ms |
9560 KB |
Output is correct |
| 10 |
Correct |
46 ms |
9812 KB |
Output is correct |
| 11 |
Correct |
78 ms |
9848 KB |
Output is correct |
| 12 |
Correct |
88 ms |
10200 KB |
Output is correct |
| 13 |
Correct |
110 ms |
10068 KB |
Output is correct |
| 14 |
Correct |
203 ms |
10584 KB |
Output is correct |
| 15 |
Correct |
212 ms |
12376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
50 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
51 ms |
131072 KB |
Execution killed with signal 9 |
| 4 |
Correct |
164 ms |
10664 KB |
Output is correct |
| 5 |
Correct |
214 ms |
11884 KB |
Output is correct |
| 6 |
Runtime error |
48 ms |
131072 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
54 ms |
131072 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
55 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
78 ms |
131072 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
72 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
91 ms |
131072 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
96 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
84 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
106 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
93 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
96 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
92 ms |
131072 KB |
Execution killed with signal 9 |
