Submission #2560600
Source Code Expand
#include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 150000; vector<int> g[N]; double dp[N]; double dp1[N]; double dp2[N]; double ans[N]; // †全方位木DP†はO(N)頂点からやると落とされちゃうめう void dfs(int i, int p = -1) { int sz = (g[i].size() - (p != -1)); for(int j : g[i]) if(j != p) { dfs(j, i); dp[i] += (1 + dp1[j]); dp1[i] += (1 + dp1[j]) / sz; } } void dfs2(int i, int p = -1) { int sz = (g[i].size() - (p != -1)); ans[i] = dp[i] + (p != -1 ? dp2[i] : 0); for(int j : g[i]) if(j != p) { dp2[j] = 1 + (ans[i] - (1 + dp1[j])) / (g[i].size() - 1); dfs2(j, i); //// } ans[i] /= g[i].size(); } int main() { ios::sync_with_stdio(false), cin.tie(0); int n; cin >> n; for(int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; g[a].emplace_back(b); g[b].emplace_back(a); } dfs(0); dfs2(0); cout << fixed << setprecision(7); for(int i = 0; i < n; i++) cout << ans[i] << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - Driving on a Tree |
User | luma |
Language | C++14 (GCC 5.4.1) |
Score | 190 |
Code Size | 1058 Byte |
Status | WA |
Exec Time | 381 ms |
Memory | 20480 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 190 / 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 | AC | 3 ms | 6400 KB |
sub1_in2.txt | AC | 6 ms | 6528 KB |
sub1_in3.txt | AC | 312 ms | 18304 KB |
sub2_in1.txt | AC | 5 ms | 6528 KB |
sub2_in2.txt | WA | 5 ms | 6528 KB |
sub3_in1.txt | WA | 347 ms | 13952 KB |
sub3_in2.txt | AC | 368 ms | 15220 KB |
sub3_in3.txt | AC | 381 ms | 20480 KB |