Submission #1535922


Source Code Expand

#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mt make_tuple
#define INF 2000000000
#define INFL 1000000000000000000LL
#define EPS (1e-8)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<P> > vvP;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
//*
// シンプルな構文解析用
typedef string::const_iterator State;
class ParseError {};
//*/
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int N;
Graph G;

vd dp;


void dfs1(int pos, int par) {
	if (pos != 0 && G[pos].size() == 1) return;
	for (auto edge : G[pos]) {
		if (edge.to == par)continue;
		dfs1(edge.to, pos);
		dp[pos] += dp[edge.to];
	}
	if (pos == 0) {
		dp[pos] /= G[pos].size();
	}
	else {
		dp[pos] /= (G[pos].size() - 1);
	}
	dp[pos] += 1;
}

void dfs2(int pos, int par, double add) {
	if (pos != 0) {
		dp[pos] = (dp[pos] * (G[pos].size() - 1) + add) / G[pos].size();
	}
	for (auto edge : G[pos]) {
		if (edge.to == par)continue;
		if (G[pos].size() == 1) {
			dfs2(edge.to, pos, 1.0);
		}
		else {
			dfs2(edge.to, pos, 1+(G[pos].size()*dp[pos]-(1+dp[edge.to]))/(G[pos].size()-1));
		}
	}
}

int main(void) {
	cin >> N;
	G = Graph(N);
	dp = vd(N, 0);
	rep(i, N - 1) {
		int s, t;
		cin >> s >> t;
		s--; t--;
		G[s].push_back(Edge{ s,t,1 });
		G[t].push_back(Edge{ t,s,1 });
	}
	dfs1(0, -1);
	dfs2(0, -1, 0);

	cout << fixed << setprecision(14);
	rep(i, N) {
		cout << dp[i] << endl;
	}

	return 0;
}

Submission Info

Submission Time
Task D - Driving on a Tree
User furuya1223
Language C++14 (GCC 5.4.1)
Score 800
Code Size 2548 Byte
Status AC
Exec Time 523 ms
Memory 20352 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 1 ms 256 KB
sub1_in2.txt AC 5 ms 384 KB
sub1_in3.txt AC 416 ms 14336 KB
sub2_in1.txt AC 4 ms 384 KB
sub2_in2.txt AC 4 ms 384 KB
sub3_in1.txt AC 523 ms 13568 KB
sub3_in2.txt AC 455 ms 13872 KB
sub3_in3.txt AC 497 ms 20352 KB