#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
#include<array>
using namespace std;
const int MAX_N=2e5+3;
const int MAX_R=447;
vector<pair<int,int>>regions;
vector<int>nodes[MAX_N];
int calc[MAX_R+3][MAX_N];
vector<int>s[MAX_N];
int in[MAX_N];
int out[MAX_N];
int ver[MAX_N];
int T;
vector<int>g[MAX_N];
int cnt;
int n,rr,q;
int region;
int r[MAX_N];
int posregion[MAX_N];
void dfs(int u,int par)
{
if(r[u]==regions[region].second)cnt++;
else
{
calc[region][r[u]]+=cnt;
}
for(int v:g[u])
{
if(v==par)continue;
dfs(v,u);
}
}
void dfs0(int u,int par)
{
in[u]=++T;
ver[T]=u;
for(int v:g[u])
{
if(v==par)continue;
dfs0(v,u);
}
out[u]=T;
}
int query(int l,int r,int col)
{
int posl,posr,le,re;
le=0;re=s[col].size()-1;
while(le<=re)
{
int mid=(le+re)/2;
if(s[col][mid]>=l)
{
posl=mid;
re=mid-1;
}
else le=mid+1;
}
le=0;re=s[col].size()-1;
while(le<=re)
{
int mid=(le+re)/2;
if(s[col][mid]>r)
{
posr=mid;
re=mid-1;
}
else le=mid+1;
}
return (posr-posl);
}
int cntr[MAX_N];
signed main ()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>rr>>q;
cin>>r[1];
nodes[r[1]].push_back(1);
cntr[r[1]]++;
for(int i=2;i<=n;i++)
{
int x;
cin>>x>>r[i];
nodes[r[i]].push_back(i);
cntr[r[i]]++;
g[i].push_back(x);
g[x].push_back(i);
}
for(int i=1;i<=rr;i++)
{
regions.push_back({cntr[i],i});
}
sort(regions.rbegin(),regions.rend());
for(int i=0;i<rr;i++)
{
posregion[regions[i].second]=i;
if(regions[i].first>=MAX_R)
{
cnt=0;
region=i;
dfs(1,0);
}
}
dfs0(1,0);
for(int pos=1;pos<=n;pos++)
{
int u=ver[pos];
s[r[u]].push_back(pos);
}
for(int i=1;i<=rr;i++)s[i].push_back(n+1);
while(q--)
{
int r1,r2;
cin>>r1>>r2;
int ans=0;
if(regions[posregion[r1]].first>=MAX_R)
{
ans=calc[posregion[r1]][r2];
}
else
{
for(int u:nodes[r1])
{
ans+=query(in[u],out[u],r2);
}
}
cout<<ans<<"\n";
}
return 0;
}
Compilation message
regions.cpp: In function 'int query(int, int, int)':
regions.cpp:84:22: warning: 'posl' may be used uninitialized in this function [-Wmaybe-uninitialized]
84 | return (posr-posl);
| ^
regions.cpp:84:22: warning: 'posr' may be used uninitialized in this function [-Wmaybe-uninitialized]
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
8 ms |
15448 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
6 ms |
15448 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
6 ms |
15448 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
6 ms |
15448 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
5 ms |
15448 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
6 ms |
15448 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
6 ms |
15448 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
6 ms |
15448 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
7 ms |
15960 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
7 ms |
15960 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
9 ms |
16216 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
9 ms |
16728 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
10 ms |
16984 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
14 ms |
17240 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
13 ms |
19800 KB |
Time limit exceeded (wall clock) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
40 ms |
20560 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
42 ms |
20240 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
39 ms |
22320 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
12 ms |
17496 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
18 ms |
18856 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
91 ms |
21072 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
50 ms |
21072 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
110 ms |
29264 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
40 ms |
25944 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
155 ms |
36788 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
54 ms |
28876 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
75 ms |
27296 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
76 ms |
28000 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
217 ms |
30148 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
67 ms |
31928 KB |
Time limit exceeded (wall clock) |
16 |
Execution timed out |
59 ms |
37072 KB |
Time limit exceeded (wall clock) |
17 |
Execution timed out |
90 ms |
37584 KB |
Time limit exceeded (wall clock) |