Submission #1321743
Source Code Expand
#include <iostream> #include <vector> #include <string> #include <iomanip> using namespace std; int n; vector<vector<int>> edges(150000 + 10); void read() { cin >> n; for(int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; edges[x].push_back(y); edges[y].push_back(x); } } int par[150000 + 10], co[150000 + 10]; double expected[150000 + 10], result[150000 + 10]; double dfs(int node, int parent) { par[node] = parent; for(int son : edges[node]) { if(son != parent) dfs(son, node); } for(int son : edges[node]) { if(son != parent) { co[node]++; } } if(co[node]) for(int son : edges[node]) { if(son != parent) expected[node] += (1 + expected[son]) / (double)co[node]; } } void dfs1(int node, int parent) { if(node == 1) { result[1] = expected[1]; } else{ result[node] = ((double) co[node]/ ((double) (co[node] + 1))) * expected[node]; if(par[node] != 1) { double res = (double) result[par[node]] * (co[par[node]] + 1) - expected[node] - 1; res = res / (double)(co[par[node]]); res++; result[node] += 1/((double)(co[node] + 1)) * res; } else { if(par[node] == 1 && co[1] >= 2) { double res = (double) result[par[node]] * (co[par[node]]) - expected[node] - 1; res = res / (double)(co[par[node]] - 1); res++; result[node] += 1/((double)(co[node] + 1)) * res; } else { result[node] += 1/(double)(1 + co[node]); } } } for(int i : edges[node]) { if(i != parent) { dfs1(i, node); } } } void solve() { dfs1(1, 0); for(int i = 1; i <= n; i++) { cout << setprecision(15) << result[i] << endl; } } int main() { read(); dfs(1, 0); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Atcoder Handles |
User | Viorel123 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2007 Byte |
Status | WA |
Exec Time | 24 ms |
Memory | 3968 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 130 | 0 / 120 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask1 | sub1_in1.txt, sub1_in2.txt, sub1_in3.txt |
Subtask2 | sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sub1_in1.txt | WA | 3 ms | 3712 KB |
sub1_in2.txt | WA | 4 ms | 3840 KB |
sub1_in3.txt | WA | 4 ms | 3840 KB |
sub2_in1.txt | WA | 3 ms | 3712 KB |
sub2_in2.txt | WA | 14 ms | 3840 KB |
sub2_in3.txt | WA | 24 ms | 3968 KB |