Submission #1294919
Source Code Expand
/*********************************************** # # Filename: d.cpp # # Author: Comsyl - ylsong15@fudan.edu.cn # Description: --- # Create: 2017-05-20 10:05:23 ***********************************************/ #include <bits/stdc++.h> using namespace std; int n; vector<vector<int>> a; vector<double> dp; vector<double> dp2; double dfs(int cur, int par) { double ans = 0; int cnt = 0; for (auto v : a[cur]) { if (v != par) { ans += 1.0 + dfs(v, cur); ++ cnt; } } if (cnt) ans /= cnt; dp[cur] = ans; return ans; } void dfs2(int cur, int par, double back) { // cout << "cur: " << cur << " par: " << par << " back= " << back << endl; double ans = 0.0; for (auto v : a[cur]) { if (v == par) ans += back + 1.0; else ans += dp[v] + 1.0; } dp2[cur] = ans / a[cur].size(); for (auto v : a[cur]) { if (v != par) { dfs2(v, cur, (ans - dp[v]-1) / max(1, (int)a[cur].size() - 1) ); } } } int main() { cin >> n; int u, v; a = vector<vector<int>> (n); dp = vector<double>(n); dp2 = vector<double>(n); for (int i = 0; i < n-1; ++ i) { cin >> u >> v; -- u; -- v; a[u].push_back(v); a[v].push_back(u); } dfs(0, -1); dfs2(0, -1, 0); for (int i = 0; i < n; ++ i) cout << fixed << setprecision(12) << dp2[i] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Driving on a Tree |
User | comsyl |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1527 Byte |
Status | AC |
Exec Time | 505 ms |
Memory | 18816 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 | 2 ms | 256 KB |
sub1_in2.txt | AC | 5 ms | 384 KB |
sub1_in3.txt | AC | 376 ms | 14976 KB |
sub2_in1.txt | AC | 4 ms | 384 KB |
sub2_in2.txt | AC | 4 ms | 384 KB |
sub3_in1.txt | AC | 505 ms | 13056 KB |
sub3_in2.txt | AC | 443 ms | 13556 KB |
sub3_in3.txt | AC | 489 ms | 18816 KB |