oj.uz

Submission #161702

# Submission time Handle Problem Language Result Execution time Memory
161702 2019-11-03T19:12:27 Z MohamedAhmed04 Mag (COCI16_mag) C++14
0 / 120
 588 ms 185880 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e6 + 10 ;

vector< vector<int> >adj(MAX) ;
long long arr[MAX] ;
pair<long long , long long>dp[MAX] ;
int n ;

pair<long long , long long>p ;
long double x , y , z ;

long double f(pair<long long , long long>pp)
{
	long double a = pp.first * 1.00 ;
	long double b = pp.second * 1.00 ;
	return (a / b) ;
}

void dfs(int node , int par)
{
	p.first = arr[node] , p.second = 1ll ;
	dp[node] = p ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dfs(child , node) ;
		x = f(dp[child]) ;
		y = f(dp[node]) ;
		p.first = dp[child].first * arr[node] , p.second = dp[child].second+1ll ;
		z = f(p) ;
		if(x <= y && x <= z)
			dp[node] = dp[child] ;
		else if(z <= x && z <= y)
			dp[node] = p ;
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	dfs(1 , -1) ;
	long long g = __gcd(dp[1].first , dp[1].second) ;
	return cout<<dp[1].first/g<<"/"<<dp[1].second/g<<"\n" , 0 ;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Incorrect 24 ms 23928 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 24056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 490 ms 119336 KB Output isn't correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 588 ms 185880 KB Output isn't correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 488 ms 93688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 482 ms 96644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 30812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 446 ms 90772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 500 ms 94704 KB Output isn't correct
2 Halted 0 ms 0 KB -