#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);
freopen("regions.in","r",stdin);
freopen("regions.out","w",stdout);
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:49: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]
49 | for (int i=0;i<V.size();i++)
| ~^~~~~~~~~
regions.cpp:65: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]
65 | for (int i=0;i<ve[r2].size();i++){
| ~^~~~~~~~~~~~~~
regions.cpp:66: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]
66 | while (j<ve[r1].size()){
| ~^~~~~~~~~~~~~~
regions.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen("regions.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen("regions.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
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 |
Incorrect |
17 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
16 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
14 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
16 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
14 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
14 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
15 ms |
108460 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
14 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
14 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
14 ms |
108376 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
19 ms |
108628 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
17 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
14 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
16 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
15 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
14 ms |
108376 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
14 ms |
108376 KB |
Unexpected end of file - int32 expected |
