#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int crit = 447;
const int maxn = 2e5+3;
const int maxr = 25003;
int i,j,p,q,n,m,R,Q,k,tin[maxn],tout[maxn],br,cnt[crit+3][maxr],hora[maxn],type[maxn],cur,d,nom[maxn];
vector <int> v[maxn];
vector <int> vid[maxr];
vector <int> kraishta[maxr];
void dfs(int u)
{
tin[u]=++br;
for(auto i:v[u])
dfs(i);
tout[u]=++br;
kraishta[type[u]].push_back(tin[u]);
}
void dfs2(int u)
{
cout<<i<<" "<<nom[i]<<" "<<type[u]<<" "<<cur<<endl;
cnt[nom[i]][type[u]]+=cur;
if(type[u]==i)
cur++;
for(auto j:v[u])
dfs2(j);
if(type[u]==i)
cur--;
}
int calc()
{
int ans = 0;
for(auto i:vid[p])
{
int l = lower_bound(kraishta[q].begin(),kraishta[q].end(),tin[i]) - kraishta[q].begin();
int r = lower_bound(kraishta[q].begin(),kraishta[q].end(),tout[i]+1) - kraishta[q].begin() - 1;
//cout<<i<<" "<<tin[i]<<" "<<tout[i]<<" "<<l<<" "<<r<<" "<<kraishta[q][l]<<" "<<kraishta[q][r]<<endl;
if(l>r)continue;
l = max(0,l);l = min(l,(int)kraishta[q].size()-1);
r = max(0,r);r = min(r,(int)kraishta[q].size()-1);
ans+=r-l+1;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>R>>Q;
cin>>p;
hora[p]++;type[1] = p;vid[p].push_back(1);
for(i=2;i<=n;i++)
{
cin>>p>>q;
hora[q]++;
type[i] = q;
vid[q].push_back(i);
v[p].push_back(i);
}
dfs(1);
for(i=1;i<=R;i++)
{
if(hora[i]>=crit)
{
// cur = 0;
nom[i]=++d;
dfs2(1);
}
}
for(i=1;i<=n;i++)
sort(kraishta[i].begin(),kraishta[i].end());
while(Q--)
{
cin>>p>>q;
if(hora[p]>crit)
cout<<cnt[nom[p]][q]<<endl;
else
cout<<calc()<<endl;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3 ms |
6096 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
4 ms |
6096 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
3 ms |
6096 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
4 ms |
6096 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
3 ms |
6224 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
4 ms |
6224 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
4 ms |
6224 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
3 ms |
6224 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
4 ms |
6736 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
5 ms |
6736 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
6 ms |
6992 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
8 ms |
7504 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
8 ms |
7120 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
14 ms |
7760 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
15 ms |
10304 KB |
Time limit exceeded (wall clock) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
18 ms |
10832 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
22 ms |
9692 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
20 ms |
12728 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
13 ms |
7840 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
12 ms |
9424 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
17 ms |
9136 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
21 ms |
10320 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
26 ms |
15200 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
49 ms |
15680 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
50 ms |
20800 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
60 ms |
15548 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
57 ms |
17004 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
57 ms |
17216 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
73 ms |
17100 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
55 ms |
21560 KB |
Time limit exceeded (wall clock) |
16 |
Execution timed out |
72 ms |
26864 KB |
Time limit exceeded (wall clock) |
17 |
Execution timed out |
55 ms |
25556 KB |
Time limit exceeded (wall clock) |