Submission #1292346
Source Code Expand
#include<cstdio>
#include<vector>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using edge_t=pair<int,double>;
using vve=vector<vector<edge_t> >;
double solve_r(vve& v, int cur, int prev)
{
double ret, r;
int n;
n=v[cur].size();
if(prev>=0) n--;
if(n==0)
{
return 0.0;
}
ret=0.0;
r=1.0/n;
for(auto& e: v[cur])
{
if(e.first==prev) continue;
if(e.second<0)
{
e.second=solve_r(v, e.first, cur);
}
ret+=(e.second+1)*r;
}
return ret;
}
void solve(vector<double>& r, vve& v)
{
for(int i=1;i<v.size();i++)
{
for(auto& e: v[i])
{
if(e.second<0)
{
e.second=solve_r(v, e.first, i);
}
r[i]+=e.second+1;
}
r[i]/=v[i].size();
}
}
int main(void)
{
vector<double> r;
vve v;
int n, a, b;
while(scanf("%d", &n)==1)
{
v.clear();
v.resize(n+1);
r.clear();
r.resize(n+1);
for(int i=0;i<n-1;i++)
{
scanf("%d%d", &a, &b);
v[a].push_back(make_pair(b, -1.0));
v[b].push_back(make_pair(a, -1.0));
}
solve(r, v);
for(int i=1;i<=n;i++)
{
printf("%f\n", r[i]);
}
}
return 0;
}
Submission Info
Submission Time
2017-05-18 01:20:56+0900
Task
D - Driving on a Tree
User
myanta
Language
C++14 (GCC 5.4.1)
Score
410
Code Size
1181 Byte
Status
TLE
Exec Time
1056 ms
Memory
20352 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:73:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
^
Judge Result
Set Name
Subtask1
Subtask2
Subtask3
Score / Max Score
190 / 190
220 / 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
256 KB
sub1_in2.txt
AC
2 ms
384 KB
sub1_in3.txt
AC
107 ms
15616 KB
sub2_in1.txt
AC
2 ms
384 KB
sub2_in2.txt
AC
2 ms
384 KB
sub3_in1.txt
AC
110 ms
13824 KB
sub3_in2.txt
TLE
1056 ms
14448 KB
sub3_in3.txt
AC
89 ms
20352 KB