Submission #1570232
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<int> G[150000]; double sum1[150000]; double sum2[150000]; double dp1[150000]; double ans[150000]; double dfs1(int v, int p){ int M = G[v].size(); if(p != -1) M--; if(M == 0) return 0; for(auto c : G[v]){ if(c == p) continue; sum1[v] += dfs1(c, v) + 1; } return dp1[v] = sum1[v] / M; } void dfs2(int v, int p){ for(auto c : G[v]){ if(c == p) continue; sum2[v] += dp1[c] + 1.0; } if(p != -1){ if(G[p].size() != 1){ sum2[v] += (sum2[p] - (dp1[v] + 1.0)) / (G[p].size() - 1) + 1.0; } else{ sum2[v] += 1.0; } } ans[v] = sum2[v] / G[v].size(); for(auto c : G[v]){ if(c != p) dfs2(c, v); } } int main(){ cin.tie(0); ios::sync_with_stdio(false); #ifdef LOCAL std::ifstream in("in"); std::cin.rdbuf(in.rdbuf()); #endif int N; cin >> N; for(int i = 0; i < N - 1; i++){ int a, b; cin >> a >> b; a--, b--; G[a].push_back(b); G[b].push_back(a); } dfs1(0, -1); dfs2(0, -1); for(int i = 0; i < N; i++){ cout << fixed << setprecision(15) << ans[i] << endl; } }
Submission Info
Submission Time | |
---|---|
Task | D - Driving on a Tree |
User | femto16 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1155 Byte |
Status | AC |
Exec Time | 419 ms |
Memory | 20480 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 | 6400 KB |
sub1_in2.txt | AC | 6 ms | 6528 KB |
sub1_in3.txt | AC | 324 ms | 17920 KB |
sub2_in1.txt | AC | 5 ms | 6528 KB |
sub2_in2.txt | AC | 5 ms | 6528 KB |
sub3_in1.txt | AC | 419 ms | 15872 KB |
sub3_in2.txt | AC | 382 ms | 15476 KB |
sub3_in3.txt | AC | 401 ms | 20480 KB |