oj.uz

Submission #246189

# Submission time Handle Problem Language Result Execution time Memory
246189 2020-07-08T10:44:16 Z NONAME Mag (COCI16_mag) C++14
120 / 120
 510 ms 150684 KB 
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6 + 100;

ll a[N], ap, aq, mx[N], mx1[N], mx2[N];
int n;
vector <int> g[N];

bool smaller(ll x, ll y) { return (x * aq) < (y * ap); }

void dfs(int v, int pr) {
    for (int u : g[v]) {
        if (u == pr)
            continue;
        dfs(u, v);

        if (mx[u] > mx1[v]) swap(mx1[v], mx2[v]), mx1[v] = mx[u];
            else if (mx[u] > mx2[v]) mx2[v] = mx[u];
    }

    if (a[v] == 1) mx[v] = mx1[v] + 1;
        else mx[v] = 0;
}

void dfs(int v, int pr, ll cur) {
    for (int u : g[v]) {
        if (u == pr)
            continue;
        ll cr = 0;

        if (a[v] == 1) {
            if (mx[u] == mx1[v]) cr = max(cur + 1, mx2[v] + 1);
                else cr = max(cur + 1, mx1[v] + 1);
        }

        dfs(u, v, cr);
    }

    ll a1 = mx1[v], a2 = mx2[v];

    if (cur > a1) swap(a1, a2), a1 = cur;
        else if (cur > a2) a2 = cur;

    if (smaller(a[v], a1 + a2 + 1)) {
        ap = a[v];
        aq = a1 + a2 + 1;
    }
}

int main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;

        g[v].push_back(u);
        g[u].push_back(v);
    }

    for (int i = 0; i < n; ++i)
        cin >> a[i];

    if (*min_element(a, a + n) > 1)
        return void(cout << *min_element(a, a + n) << "/1\n"), 0;

    ap = aq = 1;

    dfs(0, 0);
    dfs(0, 0, 0);

    ll gc = __gcd(ap, aq);

    cout << ap / gc << "/" << aq / gc << "\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 98936 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 492 ms 150684 KB Output is correct

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 85976 KB Output is correct
2 Correct 341 ms 69752 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 87140 KB Output is correct
2 Correct 94 ms 30332 KB Output is correct
3 Correct 505 ms 149112 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 30328 KB Output is correct
2 Correct 442 ms 86520 KB Output is correct
3 Correct 363 ms 55672 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 81648 KB Output is correct
2 Correct 443 ms 85368 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 86904 KB Output is correct
2 Correct 377 ms 55928 KB Output is correct