QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#210522#6538. Lonely Kingucup-team1004WA 2ms8388kbC++142.2kb2023-10-11 15:48:042023-10-11 15:48:04

Judging History

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

  • [2023-10-11 15:48:04]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8388kb
  • [2023-10-11 15:48:04]
  • 提交

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;
}

详细

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'