|

General

# Author Problem Lang Verdict Time Memory Sent Judged
76082689 Practice:
Karan123
839C - 36 GNU C++11 Wrong answer on test 6 343 ms 4968 KB 2020-04-10 14:18:31 2020-04-10 14:18:31

→ Source
#include<bits/stdc++.h>
using namespace std;
#define N 100001
vector<vector<long int>>a(N);
vector<long double>prob(N);
vector<long int>steps(N);
vector<long int>visited(N);
int dfs(int index){
if(visited[index]==1)
return 0;
int i;
// cout<<"index:"<<index<<"\n";
visited[index]=1;
for(i=0;i<a[index].size();i++){
// cout<<"Child:"<<a[index][i]<<"a[index].size():"<<a[index].size()<<"\n";
if(visited[a[index][i]]==0){
if(index==0)
prob[a[index][i]] = prob[index]*(1.0/(a[index].size()));
else
prob[a[index][i]] = prob[index]*(1.0/(a[index].size()-1));
steps[a[index][i]] = steps[index]+1;
// cout<<"steps:"<<steps[a[index][i]]<<"prob:"<<prob[a[index][i]]<<"\n";
dfs(a[index][i]);}
}
return 0;
}
int main(){
int n;
cin>>n;
int i,x,y,j;
prob[0]=1;
for(i=0;i<n-1;i++){
cin>>x>>y;
a[x-1].push_back(y-1);
a[y-1].push_back(x-1);
// cout<<"i:"<<i<<"x:"<<x<<"y:"<<y<<"\n";
}
// cout<<"Array:\n";
// for(i=0;i<n;i++){
//     for(j=0;j<a[i].size();j++)
//     cout<<a[i][j]<<" ";
//     cout<<"\n";
// }
// cout<<"\n***********\n";
dfs(0);
long double sum = 0;
for(i=0;i<n;i++){
if(a[i].size()==1){
sum = sum + steps[i]*prob[i];
}
}
// for(i=0;i<n;i++){
//     cout<<"i:"<<i+1<<"prob[i]:"<<prob[i]<<"steps[i]:"<<steps[i]<<"\n";
// }
cout<<setprecision(6)<<sum;
return 0;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?