Submission #1590132


Source Code Expand

#include <iostream>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

#define EPS 1e-9
typedef pair<int, int> ii;

vector<vector<int> > g; vector<map<int, double> > m;
vector<map<int, double> > v;
int N;

double solve(int n, int p){
	double tot = 0, np = 0;
	if(p!=-1&&v[n][p]==1)
		return m[n][p];
	for(int x=0; x<g[n].size(); x++){
		if(g[n][x]!=p){
//			cout << n << " " << g[n][x] << endl;
//			cout << x << g[n].size() << endl;
			double res = solve(g[n][x], n);
			tot += res+1;
			np++;
		}
	}
	if(np==0){
		//endnode
		np++;
	}
	v[n][p] = 1;
//	cout << n << " " << p << " " << np << endl;
	if(p==-1)
		return (tot/((double)np));
	else
		return m[n][p] = (tot/((double)np));
}

int main(){
	cin>>N;
	g.assign(N+1, vector<int>());
	m.assign(N+1, map<int, double>());
	v.assign(N+1, map<int, double>());
	int A, B;
	for(int n=1; n<N; n++){
		cin>>A>>B;
		g[A].push_back(B);
		g[B].push_back(A);
	//	cout << A << " " << B << endl;
	}
	//for(int x=0; x<g[5].size(); x++)
	//	cout << g[5][x] << endl;
	for(int n=1; n<=N; n++){
		double r = solve(n, -1);
	//	cout << g[5][2] << endl;
		printf("%.8f\n", r);
	//	cout << n << endl;
	}
	//cout << "f" << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Driving on a Tree
User robert30
Language C++14 (GCC 5.4.1)
Score 410
Code Size 1254 Byte
Status TLE
Exec Time 1057 ms
Memory 79232 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3
Score / Max Score 190 / 190 220 / 220 0 / 390
Status
AC × 3
AC × 2
AC × 7
TLE × 1
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 3 ms 768 KB
sub1_in3.txt AC 283 ms 55936 KB
sub2_in1.txt AC 3 ms 768 KB
sub2_in2.txt AC 3 ms 768 KB
sub3_in1.txt AC 416 ms 71040 KB
sub3_in2.txt TLE 1057 ms 41972 KB
sub3_in3.txt AC 228 ms 79232 KB