Submission #1292346


Source Code Expand

#include<cstdio>
#include<vector>


using namespace std;


using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using edge_t=pair<int,double>;
using vve=vector<vector<edge_t> >;


double solve_r(vve& v, int cur, int prev)
{
	double ret, r;
	int n;

	n=v[cur].size();
	if(prev>=0) n--;
	if(n==0)
	{
		return 0.0;
	}

	ret=0.0;
	r=1.0/n;
	for(auto& e: v[cur])
	{
		if(e.first==prev) continue;
		if(e.second<0)
		{
			e.second=solve_r(v, e.first, cur);
		}
		ret+=(e.second+1)*r;
	}
	return ret;
}


void solve(vector<double>& r, vve& v)
{
	for(int i=1;i<v.size();i++)
	{
		for(auto& e: v[i])
		{
			if(e.second<0)
			{
				e.second=solve_r(v, e.first, i);
			}
			r[i]+=e.second+1;
		}
		r[i]/=v[i].size();
	}
}


int main(void)
{
	vector<double> r;
	vve v;
	int n, a, b;

	while(scanf("%d", &n)==1)
	{
		v.clear();
		v.resize(n+1);
		r.clear();
		r.resize(n+1);
		for(int i=0;i<n-1;i++)
		{
			scanf("%d%d", &a, &b);
			v[a].push_back(make_pair(b, -1.0));
			v[b].push_back(make_pair(a, -1.0));
		}
		solve(r, v);
		for(int i=1;i<=n;i++)
		{
			printf("%f\n", r[i]);
		}
	}
	return 0;
}

Submission Info

Submission Time
Task D - Driving on a Tree
User myanta
Language C++14 (GCC 5.4.1)
Score 410
Code Size 1181 Byte
Status TLE
Exec Time 1056 ms
Memory 20352 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:73:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
                         ^

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 2 ms 384 KB
sub1_in3.txt AC 107 ms 15616 KB
sub2_in1.txt AC 2 ms 384 KB
sub2_in2.txt AC 2 ms 384 KB
sub3_in1.txt AC 110 ms 13824 KB
sub3_in2.txt TLE 1056 ms 14448 KB
sub3_in3.txt AC 89 ms 20352 KB