Submission #1633828
Source Code Expand
#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)n;++i) #define each(a,b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl #define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl #define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl using namespace std; typedef pair<int,int>P; const int MAX_N = 100005; vector<int> G[MAX_N]; double dp[MAX_N]; double dp2[MAX_N]; double ans[MAX_N]; bool ha[MAX_N]; int eda[MAX_N]; void dfs(int u,int p) { int cnt = 0; int res = 0; if((int)G[u].size() == 1 && G[u][0] == p){ ha[u] = true; dp[u] = 0; return; } rep(i,G[u].size()){ if(G[u][i] != p){ cnt++; dfs(G[u][i],u); res += dp[G[u][i]]; } } eda[u] = cnt; dp[u] = res/cnt + 1; } void dfs2(int u,int p) { rep(i,G[u].size()){ if(G[u][i] != p){ if(u == 0){ if(eda[u] == 1){ dp2[G[u][i]] = 1; }else{ dp2[G[u][i]] = (dp[u]*eda[u]-(1+dp[G[u][i]]))/(eda[u]-1) + 1; } }else{ dp2[G[u][i]] = dp2[u]/eda[u] + dp[u]-(1+dp[G[u][i]])/eda[u] + 1; } ans[G[u][i]] = dp2[G[u][i]]/(eda[G[u][i]]+1) + dp[G[u][i]]*eda[G[u][i]]/(eda[G[u][i]]+1); dfs2(G[u][i],u); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; rep(i,n-1){ int a,b; cin >> a >> b; G[a-1].pb(b-1),G[b-1].pb(a-1); } dfs(0,-1); ans[0] = dp[0]; dp2[0] = 0; dfs2(0,-1); rep(i,n){ printf("%.12lf\n",ans[i]); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Driving on a Tree |
User | kopricky |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2212 Byte |
Status | RE |
Exec Time | 122 ms |
Memory | 16128 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 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 | WA | 3 ms | 3456 KB |
sub1_in2.txt | WA | 4 ms | 3584 KB |
sub1_in3.txt | WA | 120 ms | 16128 KB |
sub2_in1.txt | WA | 3 ms | 3456 KB |
sub2_in2.txt | WA | 3 ms | 3456 KB |
sub3_in1.txt | RE | 101 ms | 3456 KB |
sub3_in2.txt | RE | 122 ms | 6904 KB |
sub3_in3.txt | RE | 113 ms | 4992 KB |