oj.uz

Submission #1106242

# Submission time Handle Problem Language Result Execution time Memory
1106242 2024-10-29T15:59:09 Z nh0902 Mag (COCI16_mag) C++14
0 / 120
 482 ms 205636 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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Incorrect 5 ms 33468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 12.0

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

Subtask #7
0 / 12.0

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

Subtask #8
0 / 12.0

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

Subtask #9
0 / 12.0

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

Subtask #10
0 / 12.0

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