oj.uz

Submission #246179

# Submission time Handle Problem Language Result Execution time Memory
246179 2020-07-08T10:33:54 Z NONAME Mag (COCI16_mag) C++14
60 / 120
 534 ms 150384 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;

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) {
    ll a1 = cur, a2 = 0;

    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]);
                else cr = max(cur + 1, mx1[v]);
        }

        dfs(u, v, cr);
    }

    if (mx1[v] > a1) swap(a1, a2), a1 = mx1[v];
    if (mx2[v] > a2) a2 = mx2[v];

    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 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 424 ms 102648 KB Output isn't correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 534 ms 150384 KB Output isn't correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 89812 KB Output is correct
2 Correct 346 ms 71672 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 90904 KB Output is correct
2 Correct 95 ms 31352 KB Output is correct
3 Incorrect 533 ms 150028 KB Output isn't correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 31224 KB Output is correct
2 Correct 466 ms 89104 KB Output is correct
3 Correct 448 ms 57720 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 85272 KB Output is correct
2 Correct 462 ms 88032 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 90528 KB Output is correct
2 Correct 413 ms 57720 KB Output is correct