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 |
|
|
|
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 |