Submission #241462

#TimeUsernameProblemLanguageResultExecution timeMemory
241462VimmerMag (COCI16_mag)C++14
12 / 120
547 ms262152 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") //#pragma GCC optimize("fast-math") //#pragma GCC optimize("no-stack-protector") #define F first #define S second #define sz(x) int(x.size()) #define pb push_back #define N 1000501 #define M ll(1e9 + 7) #define inf 1e9 + 1e9 using namespace std; //using namespace __gnu_pbds; typedef long double ld; typedef long long ll; typedef short int si; typedef array <int, 3> a3; //typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; int a[N]; pair <ld, pair <ll, int> > f[N]; ld ans = -1; ll l, r; vector <int> g[N]; bool cmp(int x, int y) { return f[y].F - f[x].F > 0; } void dfs(int v, int p) { f[v] = {a[v], {a[v], 1}}; vector <int> pr; pr.clear(); for (auto it : g[v]) { if (it == p) continue; dfs(it, v); pr.pb(it); ld sum = ld(f[it].S.F) * ld(a[v]); ld kol = ld(f[it].S.S + 1); ld res = ld(sum) / ld(kol); if (f[v].F - res > 0) f[v] = {res, {sum, kol}}; } sort(pr.begin(), pr.end(), cmp); if (ans == -1 || ans - f[v].F > 0) {ans = f[v].F; l = f[v].S.F; r = f[v].S.S;} if (sz(pr) < 2) return; ll sum = f[pr[0]].S.F * f[pr[1]].S.F * a[v], kol = f[pr[0]].S.S + f[pr[1]].S.S + 1; ld res = ld(sum) / ld(kol); if (ans == -1 || ans - res > 0) {ans = res; l = sum; r = kol;} } int main() { //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout); ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].pb(y); g[y].pb(x); } for (int i = 1; i <= n; i++) cin >> a[i]; dfs(1, -1); ll gcd = __gcd(l, r); l /= gcd; r /= gcd; cout << l << "/" << r << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...