Submission #1332372
Source Code Expand
#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]+1;else
if(d[u]>1)g[v]=(f[u]*d[u]-f[v]-1)/(d[u]-1)+1;
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;
}
dfs1(1,0),dfs2(1,0);
for(printf("%.6lf\n",f[i=1]);++i<=n;)
printf("%.6lf\n",(f[i]*d[i]+g[i])/(d[i]+1));
}
Submission Info
Submission Time
2017-06-05 11:23:36+0900
Task
D - Driving on a Tree
User
ZYF1024
Language
C++14 (GCC 5.4.1)
Score
190
Code Size
700 Byte
Status
WA
Exec Time
87 ms
Memory
12032 KB
Compile Error
./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);
^
Judge Result
Set Name
Subtask1
Subtask2
Subtask3
Score / Max Score
190 / 190
0 / 220
0 / 390
Status
Set Name
Test Cases
Subtask1
sub1_in1.txt, sub1_in2.txt, sub1_in3.txt
Subtask2
sub2_in1.txt, sub2_in2.txt
Subtask3
sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt
Case Name
Status
Exec Time
Memory
sub1_in1.txt
AC
1 ms
2176 KB
sub1_in2.txt
AC
2 ms
2304 KB
sub1_in3.txt
AC
87 ms
10624 KB
sub2_in1.txt
AC
1 ms
2304 KB
sub2_in2.txt
WA
1 ms
2304 KB
sub3_in1.txt
WA
77 ms
7296 KB
sub3_in2.txt
AC
58 ms
5888 KB
sub3_in3.txt
AC
69 ms
12032 KB