Submission #133382

#	Time	Username	Problem	Language	Result	Execution time	Memory
133382		Vlatko	Mag (COCI16_mag)	C++14	120 / 120	615 ms	150932 KiB

mag

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int maxn = 1000010;

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

int n;
vector<int> adj[maxn];
int x[maxn];
int up[maxn];
int down[maxn][2];

void dfs1(int u, int p) {
	down[u][0] = down[u][1] = 0;
	for (int v : adj[u]) {
		if (v != p) {
			dfs1(v, u);
			if (x[v] == 1) {
				int res = 1 + down[v][0];
				if (res >= down[u][0]) {
					down[u][1] = down[u][0];
					down[u][0] = res;
				} else if (res > down[u][1]) {
					down[u][1] = res;
				}
			}
		}
	}
}

void dfs2(int u, int p) {
	up[u] = 0;
	if (p != -1 && x[p] == 1) {
		if (x[u] == 1 && down[p][0] == 1 + down[u][0]) {
			up[u] = max(1 + up[p], 1 + down[p][1]);
		} else {
			up[u] = max(1 + up[p], 1 + down[p][0]);
		}
	}
	for (int v : adj[u]) {
		if (v != p) {
			dfs2(v, u);
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n-1; ++i) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= n; ++i) {
		cin >> x[i];
	}
	dfs1(1, -1);
	dfs2(1, -1);
	// for (int i = 1; i <= n; ++i) {
	// 	cout << "i=" << i << " up=" << up[i] << " down[0]=" << down[i][0] << " down[1]=" << down[i][1] << endl;
	// }
	long double bestres = 1e18, res;
	ll bestp, bestq, p, q;
	for (int i = 1; i <= n; ++i) {
		vector<int> options = {down[i][0], down[i][1], up[i]};
		sort(options.rbegin(), options.rend());
		// cout << "i=" << i << " x[" << i << "]=" << x[i] << " down[0]=" << down[i][0] << " down[i][1]=" << down[i][1] << " up=" << up[i] << "\n";
		p = x[i];
		q = 1 + options[0] + options[1];
		res = (long double)p / (long double)q;
		// cout << "p=" << p << " q=" << q << " res=" << res << endl;
		if (res < bestres) {
			bestres = res;
			bestp = p;
			bestq = q;
		}
	}
	ll g = gcd(bestp, bestq);
	bestp /= g, bestq /= g;
	cout << bestp << '/' << bestq << '\n';
}

Compilation message (stderr)

mag.cpp: In function 'int main()':
mag.cpp:86:20: warning: 'bestq' may be used uninitialized in this function [-Wmaybe-uninitialized]
  bestp /= g, bestq /= g;
              ~~~~~~^~~~
mag.cpp:86:8: warning: 'bestp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  bestp /= g, bestq /= g;
  ~~~~~~^~~~

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