Submission #1438947
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #define rep(i, n) for(int i = 0; i < (n); ++i) using namespace std; typedef long double ld; int n; vector<int> t[150000]; bool used[150000]; vector<int> g[150000]; ld e[150000]; ld ans[150000]; void make_graph(int i){ used[i] = true; for(int v: t[i]){ if(!used[v]){ g[i].push_back(v); make_graph(v); } } } ld dfs(int i){ ld c = 0; for(int v: g[i]){ c += dfs(v) + 1; } return e[i] = c / max((int)g[i].size(), 1); } void solve(int i, ld u){ if(i == 0){ ans[i] = e[i]; ld s = 0; for(int v: g[i]){ s += e[v]; } for(int v: g[i]){ solve(v, g[i].size() == 1 ? 0 : (s - e[v]) / (g[i].size() - 1) + 1); } return; } ans[i] = (u + 1 + g[i].size() * e[i]) / (g[i].size() + 1); ld s = 0; for(int v: g[i]){ s += e[v]; } for(int v: g[i]){ solve(v, (s - e[v] + u) / g[i].size() + 1); } } int main(){ cin >> n; rep(i, n - 1){ int u, v; cin >> u >> v; t[u - 1].push_back(v - 1); t[v - 1].push_back(u - 1); } make_graph(0); dfs(0); solve(0, -1); rep(i, n){ cout << ans[i] << setprecision(10) << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Driving on a Tree |
User | hipokaba |
Language | C++14 (GCC 5.4.1) |
Score | 190 |
Code Size | 1444 Byte |
Status | WA |
Exec Time | 532 ms |
Memory | 24832 KB |
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 | 4 ms | 10112 KB |
sub1_in2.txt | AC | 7 ms | 10240 KB |
sub1_in3.txt | AC | 385 ms | 23296 KB |
sub2_in1.txt | WA | 7 ms | 10112 KB |
sub2_in2.txt | WA | 7 ms | 10112 KB |
sub3_in1.txt | WA | 532 ms | 21376 KB |
sub3_in2.txt | AC | 444 ms | 18420 KB |
sub3_in3.txt | AC | 488 ms | 24832 KB |