Submission #245763

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
245763	2020-07-07T10:57:33 Z	Vladikus004	Kralj (COCI16_kralj)	C++14	0 / 140	234 ms	44920 KB

kralj

#include <bits/stdc++.h>
#define int long long
#define inf 2e9
#define mp make_pair
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 1000000 + 3;
int n, z[N], p[N];
pair <ld, pii> dp[N], ans;
vector <vector <int> > v;

void solve1(int x, int pr){
    p[x] = 1;
    for (auto u: v[x]){
        if (p[u]) continue;
        if (pr != -1)
            dp[x] = min(
            mp(ld(dp[pr].second.first * z[x]) / (dp[pr].second.second + 1), mp(dp[pr].second.first * z[x], dp[pr].second.second + 1)),
            mp(ld(z[x]), mp(z[x], 1LL))
            );
        else
            dp[x] = {ld(z[x]), {z[x], 1}};
        solve1(u, x);
    }
    ans = min(ans, dp[x]);
}

void solve2(int x, int pr){
    p[x] = 1;
    for (auto u: v[x]){
        if (p[u]) continue;
        if (pr != -1)
            dp[x] = max(
            mp(ld(dp[pr].second.first * z[x]) / (dp[pr].second.second + 1), mp(dp[pr].second.first * z[x], dp[pr].second.second + 1)),
            mp(ld(z[x]), mp(z[x], 1LL))
            );
        else
            dp[x] = {ld(z[x]), {z[x], 1}};
        int gc = __gcd(dp[x].second.first, dp[x].second.second);
        dp[x].second.first /= gc;
        dp[x].second.second /= gc;
        solve2(u, x);
    }
    ans = min(ans, dp[x]);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n;
    v.resize(n);
    int st = -1;
    for (int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        --a; --b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 0; i < n; i++) if (v[i].size() == 1) st = i;
    for (int i = 0; i < n; i++) cin >> z[i];
    ans = {inf * inf, {inf, inf}};
    if (n <= 1000){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++) dp[j] = {inf * inf, {inf, inf}}, p[j] = 0;
            solve1(i, -1);
        }
    }else{
        for (int i = 0; i < n; i++) dp[i] = {inf * inf, {inf, inf}};
        solve2(st, -1);
    }
    cout << ans.second.first << "/" << ans.second.second << "\n";
}

Subtask #1

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	58 ms	27236 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	54 ms	26600 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	62 ms	32872 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	78 ms	33636 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	139 ms	37880 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	185 ms	38220 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	224 ms	42360 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	193 ms	39136 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	234 ms	44920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	185 ms	41848 KB	Execution killed with signal 11 (could be triggered by violating memory limits)