oj.uz

Submission #80548

# Submission time Handle Problem Language Result Execution time Memory
80548 2018-10-21T10:01:19 Z pzdba Mag (COCI16_mag) C++14
36 / 120
 864 ms 252736 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23932 KB Output is correct
2 Correct 24 ms 23936 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 136404 KB Output is correct
2 Incorrect 779 ms 231792 KB Output isn't correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 231792 KB Output is correct

Subtask #6
0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 231792 KB Output is correct
2 Correct 129 ms 231792 KB Output is correct
3 Correct 864 ms 252736 KB Output is correct

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 252736 KB Output is correct
2 Incorrect 668 ms 252736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 252736 KB Output is correct
2 Incorrect 633 ms 252736 KB Output isn't correct

Subtask #10
0 / 12.0

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