Submission #1724766
Source Code Expand
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<int> vi; typedef long double ld; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<int>::iterator sit; typedef map<int,int>::iterator mit; typedef vector<int>::iterator vit; vi adj[150001]; vector<ld> dpadj[150001]; ld dp[150001]; vector<ld> dp2adj[150001]; ld dp2[150001]; void dfs1(int u, int p) { ld ans = 0; ll child = 0; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if(v==p) continue; dfs1(v,u); child++; ans+=dp[v]; } if(child==0) { dp[u]=0; return ; } ans/=ld(child); ans+=1; dp[u] = ans; } void dfs2(int u, int p) { ld ans = 0; ll child = 0; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if(v==p) continue; dfs2(v,u); child++; ans+=dp[v]; } if(child==0) { return ; } for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if(v==p) continue; if(child==1) { dpadj[u][i] = 0; continue; } dpadj[u][i] = 1 + (ld(1)/ld(child-1))*(ans-dp[v]); } } void dfs3(int u, int idx, int p) { ll child=0; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if(v==p) continue; child++; } if(p==-1) { dp2[u] = dp[u]; } else { dp2[u] = (ld(child)/ld(child+1))*dp[u] + (ld(1)/ld(child+1))*(dp2adj[p][idx]+1); } for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if(v==p) continue; if(p==-1) { dp2adj[u][i] = dpadj[u][i]; } else { dp2adj[u][i] = ld(child-1)/ld(child)*dpadj[u][i] + ld(1)/ld(child)*(dp2adj[p][idx]+1); } } for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if(v==p) continue; dfs3(v,i,u); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin>>n; for(int i=0;i<n-1;i++) { int u, v; cin>>u>>v; u--; v--; adj[u].pb(v); adj[v].pb(u); } for(int i = 0; i < n; i++) { dpadj[i].resize(int(adj[i].size())); dp2adj[i].resize(int(adj[i].size())); } dfs1(0,-1); dfs2(0,-1); dfs3(0,0,-1); for(int i = 0; i < n; i++) { cout<<fixed<<setprecision(10)<<dp2[i]<<'\n'; } }
Submission Info
Submission Time | |
---|---|
Task | D - Driving on a Tree |
User | vjudge4 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 2386 Byte |
Status | AC |
Exec Time | 221 ms |
Memory | 44416 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 | 6 ms | 11392 KB |
sub1_in2.txt | AC | 7 ms | 11648 KB |
sub1_in3.txt | AC | 197 ms | 37248 KB |
sub2_in1.txt | AC | 7 ms | 11520 KB |
sub2_in2.txt | AC | 7 ms | 11520 KB |
sub3_in1.txt | AC | 221 ms | 36224 KB |
sub3_in2.txt | AC | 135 ms | 36724 KB |
sub3_in3.txt | AC | 163 ms | 44416 KB |