QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#816693#9532. 长野原龙势流星群Naganohara_Yoimiya0 0ms0kbC++203.6kb2024-12-16 16:44:162024-12-16 16:44:17

Judging History

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

  • [2024-12-16 16:44:17]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-12-16 16:44:16]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second
#define ull unsigned long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,ll y,int p=mod){
	int ans=1;y%=(p-1);
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937_64 rnd(20070819);
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=2e5+5;
vector<int>G[N];
int n;
ll a[N];

struct Info{
	int cnt;ll sum;
	Info(int C=0,ll S=0):cnt(C),sum(S){}
	bool operator<(const Info &rhs)const{
		return sum*rhs.cnt>rhs.sum*cnt;
	}
};
Info operator+(Info A,Info B){return Info(A.cnt+B.cnt,A.sum+B.sum);}
ll Cross(Info A,Info B){return A.cnt*B.sum-A.sum*B.cnt;}

struct Node{int ls,rs,siz;ull rk;Info val,sum;};

Node d[N*20];int tot=0,b[N*20],cnt;
#define ls(p) (d[p].ls)
#define rs(p) (d[p].rs)
int build(Info v){
	int p=cnt>0?b[cnt--]:++tot;d[p].ls=d[p].rs=0;
	d[p].siz=1,d[p].rk=rnd();
	d[p].val=d[p].sum=v;
	return p;
}
void del(int p){d[p].val=d[p].sum=Info(0,0),d[p].siz=d[p].rk=d[p].ls=d[p].rs=0;b[++cnt]=p;}
void pushup(int p){
	d[p].siz=d[ls(p)].siz+d[rs(p)].siz+1;
	d[p].sum=d[ls(p)].sum+d[rs(p)].sum+d[p].val;
}
void split(int p,int k,int &x,int &y){
	if(!p){x=y=0;return ;}
	if(k<=d[ls(p)].siz)y=p,split(ls(p),k,x,ls(y)),pushup(y);
	else x=p,split(rs(p),k-d[ls(p)].siz-1,rs(x),y),pushup(x);
}
int merge(int p,int q){
	if(!p||!q)return p^q;
	if(d[p].rk<d[q].rk){d[p].rs=merge(rs(p),q);pushup(p);return p;}
	else{d[q].ls=merge(p,ls(q));pushup(q);return q;}
}
int getrk(Info v,int p){
	if(!p)return 0;
	if(d[p].val<v)return d[ls(p)].siz+1+getrk(v,rs(p));
	return getrk(v,ls(p));
}
void ins(Info v,int &p){
	int k=getrk(v,p);
	int A=0,B=0;
	split(p,k,A,B);
	int q=build(v);
	p=merge(A,merge(q,B));
}
void Merge(int &p,int q){
	if(!q)return ;
	ins(d[q].val,p);
	Merge(p,ls(q)),Merge(p,rs(q));
}
void Del(int p){
	if(!p)return ;
	Del(ls(p)),Del(rs(p)),del(p);
}
int getmn(int p){
	if(!p)return 0;
	if(!ls(p))return p;
	return getmn(ls(p));
}
void pop(int &p){
	int A=0,B=0;
	split(p,1,A,B);
	p=B;
}

Info Ans;
void qry(int p,Info pf){
	if(!p)return ;
	Info L=d[ls(p)].sum;
	if(Cross(pf+L,d[p].val)>=0)Ans=pf+L+d[p].val,qry(rs(p),pf+L+d[p].val);
	else qry(ls(p),pf);
}
#undef ls
#undef rs

int root[N],sz[N];
Info ans[N];
void dfs(int u){
	sz[u]=1;
	for(int v:G[u])dfs(v),sz[u]+=sz[v];
	sort(G[u].begin(),G[u].end(),[&](int x,int y){return sz[x]>sz[y];});
	for(int v:G[u]){
		if(!root[u])root[u]=root[v];
		else Merge(root[u],root[v]),Del(root[v]);
	}

	int p=getmn(root[u]);ll c0=1,s0=a[u];
	while(p){
		if(Cross(d[p].val,Info(c0,s0))<=0){
			c0+=d[p].val.cnt,s0+=d[p].val.sum;
			pop(root[u]),p=getmn(root[u]);
		}
		else break;
	}
	ins(Info(c0,s0),root[u]);
	
	p=getmn(root[u]);assert(d[root[u]].siz<=200);
	ans[u]=d[p].val;
}

ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

signed main(void){
	
	n=read();
	for(int i=2;i<=n;i++){int p=read();G[p].emplace_back(i);}
	for(int i=1;i<=n;i++)a[i]=read();

	dfs(1);
	for(int i=1;i<=n;i++){
		auto [x,y]=ans[i];
		ll g=gcd(x,y);x/=g,y/=g;
		double dx=x,dy=y;
		cout<<fixed<<setprecision(6)<<dy/dx<<'\n';
	}

	return 0;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

2000
1 2 2 4 5 2 3 6 4 2 7 2 8 14 8 12 1 14 4 14 8 18 9 2 7 22 20 22 14 29 28 16 6 21 23 6 21 14 13 9 1 4 18 13 2 39 21 33 18 20 38 27 27 1 49 5 51 3 31 24 10 42 2 44 13 9 35 66 27 60 67 59 29 40 53 2 33 43 26 43 62 16 78 45 14 10 73 69 41 35 25 26 2 70 54 1 54 48 5 36 44 28 90 29 51 51 93 82 95 45 ...

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #32:

score: 0
Runtime Error

input:

200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #2:

0%