Submission #1321744
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 | D - Driving on a Tree |
User | Viorel123 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 2007 Byte |
Status | AC |
Exec Time | 525 ms |
Memory | 18048 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 | 3840 KB |
sub1_in2.txt | AC | 6 ms | 3840 KB |
sub1_in3.txt | AC | 376 ms | 14720 KB |
sub2_in1.txt | AC | 5 ms | 3840 KB |
sub2_in2.txt | AC | 6 ms | 3840 KB |
sub3_in1.txt | AC | 525 ms | 14464 KB |
sub3_in2.txt | AC | 488 ms | 13044 KB |
sub3_in3.txt | AC | 516 ms | 18048 KB |