QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491734 | #6538. Lonely King | totest | WA | 3ms | 19140kb | C++14 | 2.5kb | 2024-07-25 21:38:48 | 2024-07-25 21:38:48 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,M=1e6,inf=2e18;
struct line{
int k,b;
}d[N];
struct tree{
int id,ls,rs,lz;
};
int calc(int id,int x){return d[id].k*x+d[id].b;}
int cmp(int id1,int id2,int x){return calc(id1,x)<calc(id2,x);}
bool ext[N];
struct LiChaoTree{
#define mid (l+r>>1)
tree t[N*40];
int top;
vector<int>tc;
void ch(int k,int z){
if(!k)return;
d[t[k].id].b+=z;t[k].lz+=z;
}
void pushdown(int k){
if(!t[k].lz)return;
ch(t[k].ls,t[k].lz),ch(t[k].rs,t[k].lz);
t[k].lz=0;
}
void del(int k){
if(!k)return;
pushdown(k);
del(t[k].ls);del(t[k].rs);
t[k]=(tree){0,0,0,0};
tc.push_back(k);
}
int newnode(){
if(!tc.size())return ++top;
int x=tc.back();tc.pop_back();
return x;
}
int add(int k,int l,int r,int id){
if(!k)k=newnode();
pushdown(k);
if(!t[k].id){t[k].id=id,ext[id]=1;return k;}
if(cmp(id,t[k].id,mid))swap(t[k].id,id),swap(ext[id],ext[t[k].id]);
if(l==r)return k;
if(cmp(id,t[k].id,l))t[k].ls=add(t[k].ls,l,mid,id);
if(cmp(id,t[k].id,r))t[k].rs=add(t[k].rs,mid+1,r,id);
return k;
}
int qry(int k,int l,int r,int x){
if(!k)return inf;
pushdown(k);
int ans=calc(t[k].id,x);
if(l==r)return ans;
if(mid>=x)ans=min(ans,qry(t[k].ls,l,mid,x));
else ans=min(ans,qry(t[k].rs,mid+1,r,x));
return ans;
}
}T;
int rt[N];
int n,c[N];
int siz[N],son[N];
int dfn[N],num;
int cans[N];
vector<int>G[N];
void prep(int u){
dfn[u]=inf;
if(!G[u].size())dfn[u]=++num,siz[u]=1;
for(auto v:G[u]){
prep(v);
siz[u]+=siz[v];
dfn[u]=min(dfn[u],dfn[v]);
if(siz[son[u]]<siz[v])son[u]=v;
}
}
void dfs(int u){
if(!son[u]){
d[dfn[u]]=(line){c[u],0};
rt[u]=T.add(rt[u],1,M,dfn[u]);
return;
}
int sum=0;
for(auto v:G[u]){
dfs(v);
cans[v]=T.qry(rt[v],1,M,c[u]);
sum+=cans[v];
}
for(auto v:G[u]){
T.ch(rt[v],sum-cans[v]);
// if(v!=son[u])T.del(rt[v]);
}
rt[u]=rt[son[u]];
for(auto v:G[u]){
if(v==son[u])continue;
for(int j=dfn[v];j<=dfn[v]+siz[v]-1;j++)
if(ext[j])ext[j]=0,rt[u]=T.add(rt[u],1,M,j);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=2,x;i<=n;i++){
cin>>x;
G[x].push_back(i);
}
for(int i=1;i<=n;i++)cin>>c[i];
prep(1);
dfs(1);
cout<<T.qry(rt[1],1,M,c[1])<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 19140kb
input:
4 1 1 2 2 1 3 2
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 16644kb
input:
50 1 2 1 1 2 1 6 3 7 5 11 11 8 10 7 8 9 7 17 2 18 4 23 8 17 21 3 19 2 4 21 18 1 26 21 36 26 24 7 7 29 27 19 29 36 11 29 42 21 15 31 15 40 15 33 2 33 15 6 50 48 33 6 43 36 19 37 28 32 47 50 8 26 50 44 50 31 32 44 22 15 46 11 33 38 22 27 43 29 8 1 21 31 28 26 39 29 39 42
output:
1525
result:
wrong answer 1st numbers differ - expected: '22728', found: '1525'