Submission #1590159


Source Code Expand

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>

using namespace std;

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

vector<vector<int> > g; vector<unordered_map<int, double> > m;
vector<unordered_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(){
	iostream::sync_with_stdio(false); cin.tie(0);
	cin>>N;
	g.assign(N+1, vector<int>());
	m.assign(N+1, unordered_map<int, double>());
	v.assign(N+1, unordered_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 A - Atcoder Handles
User robert30
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1352 Byte
Status RE
Exec Time 99 ms
Memory 1536 KB

Judge Result

Set Name Subtask1 Subtask2
Score / Max Score 0 / 130 0 / 120
Status
RE × 3
RE × 6
Set Name Test Cases
Subtask1 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt
Subtask2 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt
Case Name Status Exec Time Memory
sub1_in1.txt RE 97 ms 256 KB
sub1_in2.txt RE 99 ms 384 KB
sub1_in3.txt RE 96 ms 384 KB
sub2_in1.txt RE 98 ms 256 KB
sub2_in2.txt RE 96 ms 896 KB
sub2_in3.txt RE 96 ms 1536 KB