QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#210522 | #6538. Lonely King | ucup-team1004 | WA | 2ms | 8388kb | C++14 | 2.2kb | 2023-10-11 15:48:04 | 2023-10-11 15:48:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=2e5+10,INF=1e9;
int n,a[N],b[N];
vector<int>to[N];
int fa[N],dep[N],son[N],siz[N],top[N];
int Min(int x,int y){
return a[x]<a[y]?x:y;
}
void dfs1(int u){
b[u]=to[u].size();
dep[u]=dep[fa[u]]+1,siz[u]=1;
for(int v:to[u]){
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
int dft,dfn[N],pos[N];
void dfs2(int u,int t){
top[u]=t,pos[dfn[u]=++dft]=u;
if(son[u])dfs2(son[u],t);
for(int v:to[u])if(v^son[u])dfs2(v,v);
}
int t[N<<2];
void pushup(int rt){
t[rt]=Min(t[rt<<1],t[rt<<1|1]);
}
bool chk(int u){
return u==1||b[u]>1;
}
void build(int l=1,int r=n,int rt=1){
if(l==r){
t[rt]=chk(pos[l])?pos[l]:0;return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void erase(int x,int l=1,int r=n,int rt=1){
if(l==r){
t[rt]=0;return;
}
int mid=(l+r)>>1;
if(x<=mid)erase(x,l,mid,rt<<1);
else erase(x,mid+1,r,rt<<1|1);
pushup(rt);
}
int query(int L,int R,int l=1,int r=n,int rt=1){
if(L<=l&&r<=R)return t[rt];
int mid=(l+r)>>1,s=0;
if(L<=mid)s=Min(s,query(L,R,l,mid,rt<<1));
if(mid<R)s=Min(s,query(L,R,mid+1,r,rt<<1|1));
return s;
}
ll ans;
void solve(int u){
int p=0;
for(int x=u;x;x=fa[top[x]]){
p=Min(p,query(dfn[top[x]],dfn[x]));
}
// debug(u,p);
ans+=1ll*a[u]*a[p];
if(b[p]--,!chk(p)){
// debug("ers",p);
erase(dfn[p]);
}
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++){
scanf("%d",&fa[i]),to[fa[i]].push_back(i);
}
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
a[0]=INF;
dfs1(1),dfs2(1,1);
vector<int>t;
for(int i=2;i<=n;i++){
if(!b[i])t.push_back(i);
}
sort(t.begin(),t.end(),[](int x,int y){
return a[x]>a[y];
});
build();
for(int x:t)solve(x);
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8388kb
input:
4 1 1 2 2 1 3 2
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 8208kb
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:
11323
result:
wrong answer 1st numbers differ - expected: '22728', found: '11323'