oj.uz

Submission #133382

# Submission time Handle Problem Language Result Execution time Memory
133382 2019-07-20T13:14:14 Z Vlatko Mag (COCI16_mag) C++14
120 / 120
 615 ms 150932 KB 
#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

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

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24056 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 100368 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 615 ms 147872 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 147700 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 85852 KB Output is correct
2 Correct 388 ms 69496 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 88964 KB Output is correct
2 Correct 98 ms 30232 KB Output is correct
3 Correct 605 ms 150932 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 30044 KB Output is correct
2 Correct 526 ms 86312 KB Output is correct
3 Correct 482 ms 55544 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 83252 KB Output is correct
2 Correct 521 ms 87008 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 86828 KB Output is correct
2 Correct 431 ms 55672 KB Output is correct