#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=416;
int n,R,q,r1,r2,cnt[200001][25000/sz+1],c[25001][25000/sz+1],c2[25001][25000/sz+1],r[200001],p[200001],tin[200001],tout[200001],t,C[25001],pos[25001];
vector <int> ke[200001],ve[25001],V;
void dfs(int u){
tin[u]=++t;
ve[r[u]].push_back(t);
if (C[r[u]]>sz)
cnt[u][pos[r[u]]]++;
for (int v:ke[u]){
for (int i=1;i<=sz;i++)
cnt[v][i]+=cnt[u][i];
dfs(v);
}
for (int i=1;i<=sz;i++)
c[r[u]][i]+=cnt[u][i];
tout[u]=++t;
ve[r[u]].push_back(-t);
}
void dfs2(int u){
if (C[r[u]]>sz)
cnt[u][pos[r[u]]]++;
for (int v:ke[u]){
dfs2(v);
for (int i=1;i<=sz;i++)
cnt[u][i]+=cnt[v][i];
}
for (int i=1;i<=sz;i++)
c2[r[u]][i]+=cnt[u][i];
}
int32_t main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n >> R >> q;
for (int i=1;i<=n;i++){
if (i>1){
cin >> p[i];
ke[p[i]].push_back(i);
}
cin >> r[i];
C[r[i]]++;
}
for (int i=1;i<=R;i++)
V.push_back(i);
sort(V.begin(),V.end(),[](int i, int j){return C[i]>C[j];});
for (int i=0;i<V.size();i++)
pos[V[i]]=i+1;
dfs(1);
memset(cnt,0,sizeof(cnt));
dfs2(1);
while (q--){
cin >> r1 >> r2;
if (C[r1]>sz){
cout << c[r2][pos[r1]] << endl;
continue;
}
if (C[r2]>sz){
cout << c2[r1][pos[r2]] << endl;
continue;
}
int j=0,cnt=0,res=0;
for (int i=0;i<ve[r2].size();i++){
while (j<ve[r1].size()){
if (abs(ve[r1][j])>abs(ve[r2][i]))
break;
cnt+=(ve[r1][j]>0)-(ve[r1][j]<0);
j++;
}
if (ve[r2][i]>0)
res+=cnt;
}
cout << res << endl;
}
}
Compilation message
regions.cpp: In function 'int32_t main()':
regions.cpp:47:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i=0;i<V.size();i++)
| ~^~~~~~~~~
regions.cpp:63:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i=0;i<ve[r2].size();i++){
| ~^~~~~~~~~~~~~~
regions.cpp:64:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | while (j<ve[r1].size()){
| ~^~~~~~~~~~~~~~
regions.cpp: In function 'void dfs2(long long int)':
regions.cpp:31:20: warning: iteration 60 invokes undefined behavior [-Waggressive-loop-optimizations]
31 | c2[r[u]][i]+=cnt[u][i];
| ~~~~~~~~~~~^~~~~~~~~~~
regions.cpp:30:19: note: within this loop
30 | for (int i=1;i<=sz;i++)
| ~^~~~
regions.cpp:28:22: warning: iteration 60 invokes undefined behavior [-Waggressive-loop-optimizations]
28 | cnt[u][i]+=cnt[v][i];
| ~~~~~~~~~^~~~~~~~~~~
regions.cpp:27:23: note: within this loop
27 | for (int i=1;i<=sz;i++)
| ~^~~~
regions.cpp: In function 'void dfs(long long int)':
regions.cpp:18:19: warning: iteration 60 invokes undefined behavior [-Waggressive-loop-optimizations]
18 | c[r[u]][i]+=cnt[u][i];
| ~~~~~~~~~~^~~~~~~~~~~
regions.cpp:17:19: note: within this loop
17 | for (int i=1;i<=sz;i++)
| ~^~~~
regions.cpp:14:22: warning: iteration 60 invokes undefined behavior [-Waggressive-loop-optimizations]
14 | cnt[v][i]+=cnt[u][i];
| ~~~~~~~~~^~~~~~~~~~~
regions.cpp:13:23: note: within this loop
13 | for (int i=1;i<=sz;i++)
| ~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
110424 KB |
Output is correct |
| 2 |
Correct |
13 ms |
110428 KB |
Output is correct |
| 3 |
Correct |
15 ms |
110424 KB |
Output is correct |
| 4 |
Correct |
16 ms |
110424 KB |
Output is correct |
| 5 |
Correct |
16 ms |
110424 KB |
Output is correct |
| 6 |
Correct |
22 ms |
110424 KB |
Output is correct |
| 7 |
Correct |
26 ms |
110424 KB |
Output is correct |
| 8 |
Correct |
31 ms |
110424 KB |
Output is correct |
| 9 |
Correct |
41 ms |
110936 KB |
Output is correct |
| 10 |
Correct |
65 ms |
110936 KB |
Output is correct |
| 11 |
Correct |
95 ms |
111696 KB |
Output is correct |
| 12 |
Correct |
103 ms |
111972 KB |
Output is correct |
| 13 |
Correct |
128 ms |
111660 KB |
Output is correct |
| 14 |
Correct |
163 ms |
112248 KB |
Output is correct |
| 15 |
Correct |
218 ms |
115964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
119 ms |
116300 KB |
Execution killed with signal 13 |
| 2 |
Runtime error |
119 ms |
114884 KB |
Execution killed with signal 13 |
| 3 |
Runtime error |
141 ms |
117840 KB |
Execution killed with signal 13 |
| 4 |
Correct |
189 ms |
116344 KB |
Output is correct |
| 5 |
Correct |
285 ms |
118624 KB |
Output is correct |
| 6 |
Runtime error |
99 ms |
122400 KB |
Execution killed with signal 13 |
| 7 |
Runtime error |
124 ms |
124764 KB |
Execution killed with signal 13 |
| 8 |
Runtime error |
168 ms |
130232 KB |
Execution killed with signal 13 |
| 9 |
Runtime error |
180 ms |
131072 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
175 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
221 ms |
131072 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
265 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
206 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
278 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
80 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
105 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
103 ms |
131072 KB |
Execution killed with signal 9 |
