square869120Contest #4

Submission #1332383

Source codeソースコード

#include<cstdio>
const int N=150001;
int i,j,t,n,d[N],fa[N],en[N+N],nxt[N+N];
double f[N],g[N];
void dfs1(int u,int p)
{
	for(int i=fa[u];i;i=nxt[i])if(en[i]^p)
		++d[u],dfs1(en[i],u),f[u]+=f[en[i]];
	if(d[u])f[u]=f[u]/d[u]+1;
}
void dfs2(int u,int p)
{
	for(int i=fa[u],v;i;i=nxt[i])if((v=en[i])^p)
	{
		if(p)g[v]=(f[u]*d[u]-f[v]-1+g[u])/d[u];else
		if(d[u]>1)g[v]=(f[u]*d[u]-f[v]-1)/(d[u]-1);
		++g[v],dfs2(v,u);
	}
}
int main()
{
	scanf("%d",&n);
	for(;++t<n+n-1;)
	{
		scanf("%d%d",&i,&j);
		en[t]=j,nxt[t]=fa[i],fa[i]=t;
		en[++t]=i,nxt[t]=fa[j],fa[j]=t;
	}
	for(dfs1(1,0),dfs2(1,i=0);i++<n;)
		printf("%.6lf\n",g[i]?(f[i]*d[i]+g[i])/(d[i]+1):f[i]);
}

Submission

Task問題 D - Driving on a Tree
User nameユーザ名 ZYF1024
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 800
Source lengthソースコード長 686 Byte
File nameファイル名
Exec time実行時間 88 ms
Memory usageメモリ使用量 12032 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:22:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:25:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&i,&j);
^

Test case

Set

Set name Score得点 / Max score Cases
Subtask1 190 / 190 sub1_in1.txt,sub1_in2.txt,sub1_in3.txt
Subtask2 220 / 220 sub2_in1.txt,sub2_in2.txt
Subtask3 390 / 390 sub1_in1.txt,sub1_in2.txt,sub1_in3.txt,sub2_in1.txt,sub2_in2.txt,sub3_in1.txt,sub3_in2.txt,sub3_in3.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sub1_in1.txt AC 1 ms 2176 KB
sub1_in2.txt AC 2 ms 2304 KB
sub1_in3.txt AC 88 ms 10624 KB
sub2_in1.txt AC 2 ms 2304 KB
sub2_in2.txt AC 2 ms 2304 KB
sub3_in1.txt AC 78 ms 7296 KB
sub3_in2.txt AC 59 ms 5888 KB
sub3_in3.txt AC 69 ms 12032 KB