Submission #80548

#	Time	Username	Problem	Language	Result	Execution time	Memory
80548		pzdba	Mag (COCI16_mag)	C++14	36 / 120	864 ms	252736 KiB

mag

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> pll;
vector<int> g[1000005];
LL x[1000005];
pll ans;
pll dp[1000005];
LL gcd[1000005];
bool cmp(pll a, pll b){
	return (LD)a.first*b.second < (LD)b.first*a.second;
}
void dfs(int u, int p){
	vector<pll> mn;
	dp[u] = pll(x[u], 1);
	int cnt = 0;
	for(int i=0;i<g[u].size();i++){
		int v = g[u][i];
		if(v == p) continue;
		cnt++;
		dfs(v, u);
		LL d1 = dp[v].first, d2 = dp[v].second;
		d1 *= gcd[v];
		d2 *= gcd[v];
		mn.push_back(pll(d1, d2));
	}
	sort(mn.begin(), mn.end(), cmp);
	if(cnt == 0){
		dp[u] = pll(x[u], 1);
	}
	else if(cnt == 1){
		LL d1 = mn[0].first, d2 = mn[0].second;
		if((LD)d1*x[u] <= 2e18){
			d1 *= x[u];
			d2++;
			LL gc = __gcd(d1, d2);
			d1 /= gc;
			d2 /= gc;
			if(cmp(pll(d1, d2), dp[u])) dp[u] = pll(d1, d2), gcd[u] = gc;
		}
	}
	else{
		LL d1 = mn[0].first, d2 = mn[0].second;
		LL e1 = mn[1].first, e2 = mn[1].second;

		if((LD)d1*x[u] <= 2e18){
			d1 *= x[u];
			d2++;
			LL gc = __gcd(d1, d2);
			d1 /= gc;
			d2 /= gc;
			if(cmp(pll(d1, d2), dp[u])) dp[u] = pll(d1, d2), gcd[u] = gc;
			d1 *= gc;
			d2 *= gc;
			if((LD)d1*e1 <= 2e18){
				d1 *= e1;
				d2 += e2;
				LL gc = __gcd(d1, d2);
				d1 /= gc;
				d2 /= gc;
				if(cmp(pll(d1, d2), ans)) ans = pll(d1, d2);
			}
		}
	}
	if(cmp(dp[u], ans)) ans = dp[u];
}
int main(){
	ans.first = 1e18, ans.second = 1;
	int n;
	scanf("%d", &n);
	for(int i=1;i<=n-1;i++){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
		scanf("%lld", &x[i]);
		ans.first = min(ans.first, x[i]);
		gcd[i] = 1;
	}
	dfs(1, 0);
	LL g = __gcd(ans.first, ans.second);
	ans.first /= g;
	ans.second /= g;
	printf("%lld/%lld\n", ans.first, ans.second);
}

Compilation message (stderr)

mag.cpp: In function 'void dfs(int, int)':
mag.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++){
              ~^~~~~~~~~~~~
mag.cpp: In function 'int main()':
mag.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
mag.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
mag.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x[i]);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 12 / 12
• Subtask 6: 0 / 12
• Subtask 7: 12 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12