Submission #1173939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173939		Nomio	Mag (COCI16_mag)	C++20	0 / 120	244 ms	48196 KiB

mag

#include<bits/stdc++.h>
#define s second
#define f first
using namespace std;
using ll = long long;

const int maxn = 1e6 + 1;
int p[maxn], sz[maxn], a[maxn], b[maxn];
ll mul[maxn], c[maxn];

int find(int x) {
	if(p[x] == x) return x;
	return p[x] = find(p[x]);
}

int unite(int u, int v) {
	u = find(u);
	v = find(v);
	if(u == v) return 0;
	if(sz[u] > sz[v]) swap(u, v);
	p[u] = v;
	sz[v] += sz[u];
	mul[v] *= mul[u];
	return v;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	ll P = 1e18, Q = 1;
	for(int i = 1; i <= n; i++) {
		cin >> c[i];
		P = min(c[i], P);
		sz[i] = 1;
		p[i] = i;
		mul[i] = c[i];
	}
	vector<pair<ll, pair<int, int>>> vec;
	for(int i = 1; i < n; i++) {
		vec.push_back({1LL * c[a[i]] * c[b[i]], {a[i], b[i]}});
	}
	sort(vec.begin(), vec.end());
	for(pair<ll, pair<int, int>> pp : vec) {
		ll Mul = pp.f;
		int u = pp.s.f;
		int v = pp.s.s;
		int V = unite(u, v);
		if(V == 0) continue;
		if(mul[V] * Q < P * sz[V]) {
			P = mul[V];
			Q = sz[V];
			ll g = __gcd(P, Q);
			P /= g;
			Q /= g;
		}
	}
	cout << P << '/' << Q << '\n';
	return 0;
}

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