oj.uz

Submission #1106243

# Submission time Handle Problem Language Result Execution time Memory
1106243 2024-10-29T15:59:38 Z nh0902 Mag (COCI16_mag) C++14
108 / 120
 324 ms 167240 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1100000;

const long long inf = LLONG_MAX;

int n, pa[N];

long long X[N], P, Q, down[N], up[N];

vector<int> g[N];

long long pre_dfs(int u, int p) {
    long long l = 1;
    pa[u] = p;
    for (int v : g[u]) if (v != p) {
        l = max(l, pre_dfs(v, u) + 1);
    }

    if (X[u] > 1) {
        down[u] = 0;
    } else {
        down[u] = l;
    }
    //cout << u << " : " << down[u] << "\n";
    return down[u];
}

void BFS(int u, int p) {

    long long l1 = up[pa[u]];
    long long l2 = 0;
    for (int v : g[u]) if (v != p) {
        l2 = max(l2, down[v]);
        if (l2 > l1) swap(l1, l2);
    }

    long long new_P = X[u];
    long long new_Q = 1 + l1 + l2;
    //cout << u << " : " << new_P << " , " << new_Q;
    if (new_P * Q < new_Q * P) {
        P = new_P;
        Q = new_Q;
    }

    if (X[u] > 1) up[u] = 0;
    else up[u] = up[pa[u]] + 1;
    //cout << " , " << up[u] << "\n";
    for (int v : g[u]) if (v != p) {
        BFS(v, u);
    }
}

long long gcd(long long a, long long b) {
    long long r = b % a;
    if (r == 0) return a;
    return gcd(r, a);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    int a, b;
    for (int i = 1; i < n; i ++) {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    bool has_1 = false;
    for (int i = 1; i <= n; i ++) {
        cin >> X[i];
        if (X[i] == 1) {
            has_1 = true;
        }
    }

    if (!has_1) {
        P = X[1];
        for (int i = 1; i <= n; i ++) {
            P = min(P, X[i]);
        }
        cout << P << "/" << "1";
        return 0;
    }

    P = 1;
    Q = 1;

    pre_dfs(1, 1);
    BFS(1, 1);

    long long d = gcd(P, Q);
    cout << P/d << "/" << Q/d;

    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29264 KB Output is correct
2 Correct 5 ms 33360 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33360 KB Output is correct
2 Correct 6 ms 33360 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33360 KB Output is correct
2 Correct 324 ms 164424 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 147528 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 87020 KB Output is correct
2 Correct 180 ms 88136 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 88864 KB Output is correct
2 Correct 39 ms 42312 KB Output is correct
3 Correct 314 ms 167240 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 40784 KB Output is correct
2 Correct 240 ms 102728 KB Output is correct
3 Correct 211 ms 71456 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 85440 KB Output is correct
2 Correct 224 ms 103648 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 87560 KB Output is correct
2 Correct 204 ms 71500 KB Output is correct