oj.uz

Submission #591507

# Submission time Handle Problem Language Result Execution time Memory
591507 2022-07-07T14:14:46 Z nguyen31hoang08minh2003 Mag (COCI16_mag) C++14
24 / 120
 396 ms 206000 KB 
/*
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|
|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ |
|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |
|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |
|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |
|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ |
|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|\\\\|////|\/ /|\ \/|
|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ | \\\|/// | \/ | \/ |
|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |  \\|//  |  \/|\/  |
|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |   \|/   |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |   /|\   |
|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |  //|\\  |  /\|/\  |
|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ | ///|\\\ | /\ | /\ |
|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|////|\\\\|/\ \|/ /\|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (signed i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (signed i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (signed i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

class Fraction {
private:
    ll x, y;
public:
    Fraction(const ll a, const ll b) {
        assert(a >= 0 && b > 0);
        const ll c = __gcd(a, b);
        x = a / c;
        y = b / c;
    }

    friend bool operator > (const Fraction &a, const Fraction &b) {
        return a.x * b.y > a.y * b.x;
    }

    friend bool operator < (const Fraction &a, const Fraction &b) {
        return a.x * b.y < a.y * b.x;
    }

    friend ostream& operator << (ostream &outputStream, const Fraction &f) {
        return outputStream << f.x << '/' << f.y;
    }
};

const int maxN = 1e6 + 5;
const double oo = 1 / 0.0;

int n, a[maxN], b[maxN], x[maxN];
vi adj[maxN];

void input() {
    cin >> n;
    fore(i, 1, n) {
        cin >> a[i] >> b[i];
        adj[a[i]].pb(b[i]);
        adj[b[i]].pb(a[i]);
    }
    fort(i, 1, n)
        cin >> x[i];
}

void subtask1() {
    vi parent(n + 1), path;
    double minimum = oo;
    int target, q, g;
    ll p = 1;
    const function<void(int, double, int)> dfs = [&](const int u, const double magic, const int h) {
        if (mini(minimum, magic - log(h)))
            target = u;
        for (const int &v : adj[u]) {
            if (v == parent[u])
                continue;
            parent[v] = u;
            dfs(v, magic + log(x[v]), h + 1);
        }
    };
    fort(u, 1, n) {
        fill(all(parent), -1);
        target = -1;
        dfs(u, log(x[u]), 1);
        if (target > 0) {
            path.clear();
            for (int v = target; v != u; v = parent[v])
                path.pb(v);
            path.pb(u);
        }
    }
    q = path.size();
    for (const int &u : path) {
        g = __gcd(x[u], q);
        q /= g;
        p *= x[u] / g;
    }
    cout << p << '/' << q << '\n';
}

void subtask2() {
    Fraction res(x[1], 1);
    const function<void(int, int, int)> dfs = [&](const int u, const int parent, int h) {
        if (x[u] == 1) {
            mini(res, Fraction(1, ++h));
        } else {
            mini(res, Fraction(x[u], 1));
        }
        for (const int &v : adj[u]) {
            if (v == parent)
                continue;
            dfs(v, u, h);
        }
    };
    fort(i, 1, n)
        if (adj[i].size() <= 1) {
            dfs(i, -1, 0);
            break;
        }
    cout << res << '\n';
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    input();
    if (n <= 5000)
        subtask1();
    else
        subtask2();
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23820 KB Output is correct
2 Correct 19 ms 23800 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 23772 KB Output is correct
2 Correct 36 ms 23900 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Incorrect 396 ms 206000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 12.0

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

Subtask #7
0 / 12.0

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

Subtask #8
0 / 12.0

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

Subtask #9
0 / 12.0

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

Subtask #10
0 / 12.0

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