oj.uz

Submission #167653

# Submission time Handle Problem Language Result Execution time Memory
167653 2019-12-09T08:43:52 Z EntityIT Mag (COCI16_mag) C++14
120 / 120
 555 ms 145148 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 86316 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 555 ms 144740 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 141748 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 66532 KB Output is correct
2 Correct 348 ms 49148 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 67524 KB Output is correct
2 Correct 72 ms 7204 KB Output is correct
3 Correct 548 ms 145148 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 7160 KB Output is correct
2 Correct 477 ms 67068 KB Output is correct
3 Correct 372 ms 34276 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 61936 KB Output is correct
2 Correct 472 ms 65712 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 67324 KB Output is correct
2 Correct 353 ms 34296 KB Output is correct