Submission #1661931
Source Code Expand
#include "bits/stdc++.h" using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define ALL(v) (v).begin(),(v).end() #define MP(a,b) make_pair(a,b) typedef long long LL; typedef pair<int, int> PI; typedef vector<int> VI; const LL MOD = 1000000007LL; vector<int> G[150000]; double dp[150000]; double dp2[150000]; void dfs1(int v, int par) { int cnt = 0; rep(i, G[v].size()) { int to = G[v][i]; if (to == par) continue; dfs1(to, v); dp[v] += (dp[to] + 1); cnt++; } if (cnt > 0) dp[v] /= cnt; } void dfs2(int v, double d_par, int par) { rep(i, G[v].size()) { int to = G[v][i]; if (to == par) dp2[v] += (d_par + 1); else dp2[v] += (dp[to] + 1); } rep(i, G[v].size()) { int to = G[v][i]; if (to == par) continue; double D = dp2[v] - (dp[to] + 1); if (G[v].size() > 1) D /= (G[v].size() - 1); dfs2(to, D, v); } dp2[v] /= G[v].size(); } int main() { int N; cin >> N; rep(i, N - 1) { int u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } dfs1(0, -1); dfs2(0, 0, -1); rep(i, N) { printf("%.15lf\n", dp2[i]); } }
Submission Info
Submission Time | |
---|---|
Task | D - Driving on a Tree |
User | Div9851 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1132 Byte |
Status | AC |
Exec Time | 207 ms |
Memory | 19328 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 | 4096 KB |
sub1_in2.txt | AC | 4 ms | 4224 KB |
sub1_in3.txt | AC | 173 ms | 16640 KB |
sub2_in1.txt | AC | 4 ms | 4096 KB |
sub2_in2.txt | AC | 4 ms | 4096 KB |
sub3_in1.txt | AC | 207 ms | 13568 KB |
sub3_in2.txt | AC | 147 ms | 13172 KB |
sub3_in3.txt | AC | 192 ms | 19328 KB |