#include<bits/stdc++.h>
using namespace std;
int n,r,q;
int c[25001];
int h[200001];
vector<int> v[200001];
int curr,s;
map<pair<int,int>, int> mp;
void dfs(int i,int cnt)
{
if(h[i]==curr)cnt++;
//cout<<i<<" - "<<curr<<" "<<c[i]<<" "<<cnt<<endl;
mp[{curr,h[i]}]+=cnt;
for(int j=0;j<v[i].size();j++)
{
int nb=v[i][j];
dfs(nb,cnt);
}
}
vector<int> pos[25001],ver[200001];
int num;
int in[100001],out[100001];
void dfs2(int i)
{
in[i]=++num;
pos[h[i]].push_back(in[i]);
for(int j=0;j<v[i].size();j++)
{
int nb=v[i][j];
dfs2(nb);
}
out[i]=num;
}
int count_(int r2,int idx)
{
if(pos[r2].size()==0||pos[r2][0]>idx)return 0;
int l=0,r=pos[r2].size()-1;
int cnt=0;
while(l<=r)
{
int m=(l+r)/2;
if(pos[r2][m]<=idx)
{
cnt=m+1;
l=m+1;
}
else r=m-1;
}
return cnt;
}
void read()
{
cin>>n>>r>>q;
s=sqrt(n);
cin>>h[1];
c[h[1]]++;
ver[h[1]].push_back(1);
for(int i=2;i<=n;i++)
{
int x;
cin>>x>>h[i];
c[h[i]]++;
v[x].push_back(i);
ver[h[i]].push_back(i);
}
for(int i=1;i<=r;i++)
{
if(c[i]<s)continue;
//cout<<i<<"!"<<endl;
curr=i;
dfs(1,0);
}
dfs2(1);
for(int i=1;i<=q;i++)
{
int r1,r2;
cin>>r1>>r2;
if(c[r1]>=s)
{
cout<<mp[{r1,r2}]<<endl;
continue;
}
int sum=0;
for(int j=0;j<ver[r1].size();j++)
{
int e1=ver[r1][j];
//cout<<e1<<" - "<<in[e1]<<" "<<out[e1]<<endl;
sum+=count_(r2,out[e1])-count_(r2,in[e1]-1);
}
/*for(int j=0;j<pos[r2].size();j++)
cout<<pos[r2][j]<<" ";
cout<<endl;
cout<<endl;*/
cout<<sum<<endl;
}
}
int main()
{
read();
return 0;
}
Compilation message
regions.cpp: In function 'void dfs(int, int)':
regions.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int j=0;j<v[i].size();j++)
| ~^~~~~~~~~~~~
regions.cpp: In function 'void dfs2(int)':
regions.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int j=0;j<v[i].size();j++)
| ~^~~~~~~~~~~~
regions.cpp: In function 'void read()':
regions.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int j=0;j<ver[r1].size();j++)
| ~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10840 KB |
Output is correct |
2 |
Correct |
2 ms |
10840 KB |
Output is correct |
3 |
Correct |
3 ms |
10920 KB |
Output is correct |
4 |
Correct |
4 ms |
10840 KB |
Output is correct |
5 |
Correct |
6 ms |
10840 KB |
Output is correct |
6 |
Correct |
11 ms |
11096 KB |
Output is correct |
7 |
Correct |
16 ms |
11096 KB |
Output is correct |
8 |
Correct |
16 ms |
11096 KB |
Output is correct |
9 |
Correct |
27 ms |
11352 KB |
Output is correct |
10 |
Correct |
55 ms |
11352 KB |
Output is correct |
11 |
Correct |
81 ms |
11608 KB |
Output is correct |
12 |
Correct |
106 ms |
12120 KB |
Output is correct |
13 |
Correct |
140 ms |
11864 KB |
Output is correct |
14 |
Correct |
227 ms |
12368 KB |
Output is correct |
15 |
Correct |
227 ms |
16176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1564 ms |
15996 KB |
Output is correct |
2 |
Correct |
1871 ms |
14044 KB |
Output is correct |
3 |
Correct |
2356 ms |
18180 KB |
Output is correct |
4 |
Correct |
209 ms |
12632 KB |
Output is correct |
5 |
Correct |
275 ms |
14168 KB |
Output is correct |
6 |
Correct |
777 ms |
37080 KB |
Output is correct |
7 |
Correct |
1343 ms |
45980 KB |
Output is correct |
8 |
Correct |
1759 ms |
84020 KB |
Output is correct |
9 |
Runtime error |
83 ms |
39248 KB |
Execution killed with signal 11 |
10 |
Runtime error |
1476 ms |
131072 KB |
Execution killed with signal 9 |
11 |
Runtime error |
134 ms |
38224 KB |
Execution killed with signal 11 |
12 |
Runtime error |
143 ms |
44692 KB |
Execution killed with signal 11 |
13 |
Runtime error |
148 ms |
46124 KB |
Execution killed with signal 11 |
14 |
Runtime error |
645 ms |
89240 KB |
Execution killed with signal 11 |
15 |
Runtime error |
161 ms |
60616 KB |
Execution killed with signal 11 |
16 |
Runtime error |
174 ms |
79008 KB |
Execution killed with signal 11 |
17 |
Runtime error |
610 ms |
119372 KB |
Execution killed with signal 11 |