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 |
|
|
|
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 |