Submission #1294885
Source Code Expand
#include<iostream> #include<vector> #include<iomanip> #include<algorithm> using namespace std; vector<int> G[1<<18]; double dp [1<<18]; double dp2 [1<<18]; double dfs(int u,int p) { int cnt = 0; double ans = 0; for(int i = 0; i < G[u].size(); i ++) { if (G[u][i] == p) continue; ans += dfs(G[u][i], u) + 1; cnt ++; } return dp[u] = cnt ? ans / cnt : 1; } void dfs2(int u, int p, double a) { double ans=0; for(int i=0;i<G[u].size();i++) { if(G[u][i]==p)ans+=a; else ans+=dp[G[u][i]]; } dp2[u] = ans/G[u].size(); for(int i=0;i<G[u].size();i++) { if(G[u][i]==p)continue; dfs2(G[u][i],u, 1+(ans-dp[G[u][i]])/max(1,(int)G[u].size()-1)); } } int main() { int n; cin>>n; int u,v; for(int i = 1; i < n; i ++) { cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); dfs2(1, 0, 0); for(int i = 1; i <= n; i ++) { cout << dp2[i] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Driving on a Tree |
User | comsyl |
Language | C++14 (GCC 5.4.1) |
Score | 190 |
Code Size | 1090 Byte |
Status | WA |
Exec Time | 490 ms |
Memory | 20864 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 | 4 ms | 8448 KB |
sub1_in2.txt | AC | 7 ms | 8576 KB |
sub1_in3.txt | AC | 373 ms | 18944 KB |
sub2_in1.txt | WA | 6 ms | 8448 KB |
sub2_in2.txt | WA | 6 ms | 8448 KB |
sub3_in1.txt | WA | 490 ms | 15488 KB |
sub3_in2.txt | AC | 434 ms | 15220 KB |
sub3_in3.txt | WA | 471 ms | 20864 KB |