Submission #1573955
Source Code Expand
#include <bits/stdc++.h> using namespace std; int n; vector<vector<int>> g; using ll = long long; ll mp(int x, int y) { return (ll)x << 32 | y; } unordered_map<ll, double> dp; double rec(int u, int p) { if (dp.count(mp(u, p))) { return dp[mp(u, p)]; } double &res = dp[mp(u, p)]; res = 0; int cnt = 0; for (auto &v : g[u]) { if (v != p) ++cnt; } if (cnt == 0) { res = 0; } else { for (auto &v : g[u]) { if (v != p) { res += 1 + rec(v, u); } } res /= cnt; } return res; } int main() { while (cin >> n) { dp.clear(); g.assign(n, {}); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; --u; --v; g[u].emplace_back(v); g[v].emplace_back(u); } for (int i = 0; i < n; i++) { printf("%.10f\n", rec(i, -1)); } } }
Submission Info
Submission Time | |
---|---|
Task | D - Driving on a Tree |
User | tubo28 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1029 Byte |
Status | WA |
Exec Time | 198 ms |
Memory | 22856 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 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 | WA | 1 ms | 256 KB |
sub1_in2.txt | WA | 2 ms | 384 KB |
sub1_in3.txt | WA | 168 ms | 17316 KB |
sub2_in1.txt | WA | 2 ms | 384 KB |
sub2_in2.txt | WA | 2 ms | 384 KB |
sub3_in1.txt | WA | 198 ms | 17096 KB |
sub3_in2.txt | WA | 145 ms | 17688 KB |
sub3_in3.txt | WA | 170 ms | 22856 KB |