Submission #1572039


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

vector< int > g[150000];
double ee[150000], ans[1500000];

void dfs1(int idx, int par)
{
  double ret = 0;
  int child = 0;

  for(int &to : g[idx]) {
    if(to == par) continue;
    dfs1(to, idx);
    ret += ee[to] + 1.0;
    ++child;
  }
  ee[idx] = 0;
  if(child >= 1) ee[idx] += ret / child;
}

void dfs2(int idx, double d_par, int par)
{
  double ret = 0;
  for(int &to : g[idx]) {
    if(to == par) ret += d_par + 1.0;
    else ret += ee[to] + 1.0;
  }
  ans[idx] = ret / g[idx].size();
  for(int &to : g[idx]) {
    if(to == par) continue;
    dfs2(to, (ret - ee[to] - 1.0) / (g[idx].size() - 1), idx);
  }
}

int main()
{
  int N;
  cin >> N;
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  if(N <= 2) {
    if(N == 1) cout << 0 << endl;
    else cout << 1 << endl << 1 << endl;
    return (0);
  }

  int root = 0;
  for(int i = 0; i < N; i++) {
    if(g[i].size() >= 2) root = i;
  }

  dfs1(root, -1);
  dfs2(root, 0, -1);
  for(int i = 0; i < N; i++) {
    cout << fixed << setprecision(10) << ans[i] << endl;
  }
}

Submission Info

Submission Time
Task D - Driving on a Tree
User ei13333
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1224 Byte
Status AC
Exec Time 503 ms
Memory 20096 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3
Score / Max Score 190 / 190 220 / 220 390 / 390
Status
AC × 3
AC × 2
AC × 8
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 3 ms 6400 KB
sub1_in2.txt AC 6 ms 6528 KB
sub1_in3.txt AC 373 ms 19584 KB
sub2_in1.txt AC 6 ms 6528 KB
sub2_in2.txt AC 5 ms 6528 KB
sub3_in1.txt AC 503 ms 14208 KB
sub3_in2.txt AC 438 ms 14708 KB
sub3_in3.txt AC 475 ms 20096 KB