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
AC × 3
AC × 2
AC × 8
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