Submission #1793012
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,h[100005],L[100005],d[100005];
vector<P>edge[100005];
vector<int>za;
int ans[100005];
int dfs(int v,int u,int sum){
int ret = sum; h[v] = sum;
for(int i=0;i<edge[v].size();i++){
if(edge[v][i].fi==u) continue;
ret = max(ret,dfs(edge[v][i].fi,v,sum+edge[v][i].sc));
}
return d[v] = ret;
}
struct BIT
{
int bit[(1<<17)+5];
int f(int x)
{
return x&-x;
}
void add(int i,int x)
{
for(int s=i;s<=(1<<17);s+=f(s)) bit[s]+=x;
}
int sum(int i)
{
int res=0;
for(int s=i;s>0;s-=f(s)) res+=bit[s];
return res;
}
}bit;
void DFS(int v,int u){
int a = POSL(za,h[v]);
int zip = bit.sum((1<<17)) - bit.sum(a+1);
zip += edge[v].size();
if(u!=-1) zip--;
ans[a] = min(ans[a],zip);
for(int i=0;i<edge[v].size();i++){
if(edge[v][i].fi==u) continue;
int b = POSL(za,d[edge[v][i].fi]);
bit.add(b+1,1);
}
for(int i=0;i<edge[v].size();i++){
if(edge[v][i].fi==u) continue;
int b = POSL(za,d[edge[v][i].fi]);
bit.add(b+1,-1);
DFS(edge[v][i].fi,v);
bit.add(b+1,1);
}
for(int i=0;i<edge[v].size();i++){
if(edge[v][i].fi==u) continue;
int b = POSL(za,d[edge[v][i].fi]);
bit.add(b+1,-1);
}
return;
}
int main(){
cin>>n;
repn(i,n){
cin>>L[i];
}
for(int i=2;i<=n;i++){
int x; cin>>x;
edge[x].pb(mp(i,L[i]));
edge[i].pb(mp(x,L[i]));
}
dfs(1,-1,L[1]);
for(int i=1;i<=n;i++){
za.pb(d[i]);
za.pb(h[i]);
}
SORT(za); ERASE(za);
fill(ans,ans+100005,INF);
DFS(1,-1);
int q; cin>>q;
rep(i,q){
int x; cin>>x;
if(POSL(za,x) == za.size() || za[POSL(za,x)] != x) puts("-1");
else printf("%d\n",ans[POSL(za,x)]);
}
}
Submission Info
Submission Time |
|
Task |
I - 風船ツリー |
User |
IH19980412 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2265 Byte |
Status |
AC |
Exec Time |
426 ms |
Memory |
16244 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt |
All |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
370 ms |
9336 KB |
01-02.txt |
AC |
3 ms |
3840 KB |
01-03.txt |
AC |
3 ms |
3840 KB |
01-04.txt |
AC |
404 ms |
9336 KB |
01-05.txt |
AC |
401 ms |
9336 KB |
01-06.txt |
AC |
404 ms |
9336 KB |
01-07.txt |
AC |
410 ms |
9204 KB |
01-08.txt |
AC |
426 ms |
11128 KB |
01-09.txt |
AC |
154 ms |
8952 KB |
01-10.txt |
AC |
293 ms |
9332 KB |
01-11.txt |
AC |
345 ms |
9588 KB |
01-12.txt |
AC |
346 ms |
9588 KB |
01-13.txt |
AC |
372 ms |
16244 KB |
01-14.txt |
AC |
371 ms |
16244 KB |
01-15.txt |
AC |
372 ms |
16244 KB |
01-16.txt |
AC |
371 ms |
13176 KB |
01-17.txt |
AC |
363 ms |
13176 KB |
01-18.txt |
AC |
394 ms |
13176 KB |
01-19.txt |
AC |
300 ms |
9204 KB |
01-20.txt |
AC |
299 ms |
9460 KB |
01-21.txt |
AC |
292 ms |
9460 KB |
01-22.txt |
AC |
287 ms |
9204 KB |
01-23.txt |
AC |
280 ms |
9204 KB |
01-24.txt |
AC |
378 ms |
9460 KB |
01-25.txt |
AC |
363 ms |
9976 KB |
01-26.txt |
AC |
356 ms |
10228 KB |
01-27.txt |
AC |
349 ms |
9460 KB |
01-28.txt |
AC |
347 ms |
9716 KB |
01-29.txt |
AC |
409 ms |
9332 KB |
01-30.txt |
AC |
400 ms |
9204 KB |
01-31.txt |
AC |
399 ms |
9332 KB |
sample-01.txt |
AC |
3 ms |
3840 KB |
sample-02.txt |
AC |
3 ms |
3840 KB |