Submission #167653

#	Time	Username	Problem	Language	Result	Execution time	Memory
167653		EntityIT	Mag (COCI16_mag)	C++14	120 / 120	555 ms	145148 KiB

mag

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
#define fi first
#define se second
using LL = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count() );
const int inf = 1e9;

int n;
vector<int> x;
vector<array<int, 2> > f;
vector<vector<int> > gr;

bool smaller(pair<int, int> p1, pair<int, int> p2) {
    return p1.fi * p2.se < p1.se * p2.fi;
}

void dfs(int u, int pr, pair<int, int>& ans) {
    if (x[u] == 1) f[u][0] = 1;
    else if (x[u] == 2) f[u][1] = 1;

    for (int v : gr[u]) if (v != pr) {
        dfs(v, u, ans);

        if (f[u][0] + f[v][0] > 0) {
            if (smaller(make_pair(1, f[u][0] + f[v][0]), ans) ) ans = make_pair(1, f[u][0] + f[v][0]);
        }

        if (max(f[u][0] + f[v][1], f[u][1] + f[v][0]) > 0) {
            if (smaller(make_pair(2, max(f[u][0] + f[v][1], f[u][1] + f[v][0]) ), ans) ) ans = make_pair(2, max(f[u][0] + f[v][1], f[u][1] + f[v][0]) );
        }

        if (x[u] == 1) {
            for (int i = 0; i < 2; ++i) f[u][i] = max(f[u][i], max(0, f[v][i]) + 1);
        }
        else if (x[u] == 2) f[u][1] = max(f[u][1], max(0, f[v][0]) + 1);
    }

    if (f[u][0] > 0) {
        if (smaller(make_pair(1, f[u][0]), ans) ) ans = make_pair(1, f[u][0]);
    }
    if (f[u][1] > 0) {
        if (smaller(make_pair(2, f[u][0]), ans) ) ans = make_pair(2, f[u][0]);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    gr.assign(n, {} );
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        gr[u].emplace_back(v);
        gr[v].emplace_back(u);
    }
    x.assign(n, 0);
    for (int i = 0; i < n; ++i) cin >> x[i];

    if (!count(all(x), 1) ) {
        cout << *min_element(all(x) ) << "/1\n";
        cout.flush();
        return 0;
    }

    pair<int, int> ans{ 2, 1 };
    f.assign(n, array<int, 2>{ -inf, -inf });
    dfs(0, 0, ans);

    int gcd = __gcd(ans.fi, ans.se);
    ans.fi /= gcd; ans.se /= gcd;
    cout << ans.fi << '/' << ans.se << '\n';
    cout.flush();

    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12