QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491707#6538. Lonely KingtotestWA 0ms19376kbC++142.6kb2024-07-25 21:11:082024-07-25 21:11:09

Judging History

你现在查看的是最新测评结果

  • [2024-07-25 21:11:09]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:19376kb
  • [2024-07-25 21:11:08]
  • 提交

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];
  }
//   cout<<"*"<<u<<' '<<sum<<' '<<cans[son[u]]<<endl;
  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++) rt[u]=T.add(rt[u],1,M,j);
  }
}
signed main(){
	// freopen("input.in","r",stdin);
	// freopen("output1.out","w",stdout);
  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: 0ms
memory: 19376kb

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: 16800kb

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:

3679

result:

wrong answer 1st numbers differ - expected: '22728', found: '3679'