oj.uz

Submission #139429

# Submission time Handle Problem Language Result Execution time Memory
139429 2019-07-31T16:47:15 Z Minnakhmetov Mag (COCI16_mag) C++14
120 / 120
 577 ms 158656 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 1e6 + 5, INF = 1e9;
vector<int> g[N];
int x[N], dp[N];
ll p, q;

void dfs(int node, int anc) {
    if (anc != -1)
        g[node].erase(find(all(g[node]), anc));

    for (int to : g[node]) {
        dfs(to, node);
        dp[node] = max(dp[node], dp[to]);
    }
    if (x[node] == 1)
        dp[node]++;
    else
        dp[node] = 0;
}

void upd(ll x, ll y) {
    if (p * y > x * q) {
        p = x;
        q = y;
    }
}

void deep(int node, int up) {
    sort(all(g[node]), [=](int x, int y) {
        return dp[x] > dp[y];
    });

    if (x[node] < 3) {
        if (g[node].size() > 0) {
            upd(x[node], up + dp[g[node][0]] + 1);
        }
        if (g[node].size() > 1) {
            upd(x[node], dp[g[node][0]] + dp[g[node][1]] + 1);
        }
    }

    for (int to : g[node]) {
        int nup = 0;
        if (x[node] == 1) {
            int cur = dp[g[node][0]];

            if (to == g[node][0])
                cur = g[node].size() > 1 ? dp[g[node][1]] : 0;

            nup = max(up, cur) + 1;
        }
        deep(to, nup);
    }
}

signed main() { 
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

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

    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }

    p = *min_element(x, x + n), q = 1;

    dfs(0, -1);
    deep(0, 0);

    if (q % p == 0) {
        q /= p;
        p = 1;
    }

    cout << p << "/" << q;

    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24056 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24056 KB Output is correct
2 Correct 24 ms 23932 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 100448 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 577 ms 155496 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 155324 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 77936 KB Output is correct
2 Correct 363 ms 63804 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 81100 KB Output is correct
2 Correct 94 ms 29432 KB Output is correct
3 Correct 574 ms 158656 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 29304 KB Output is correct
2 Correct 486 ms 78728 KB Output is correct
3 Correct 378 ms 51588 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 76496 KB Output is correct
2 Correct 477 ms 79224 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 78968 KB Output is correct
2 Correct 390 ms 51704 KB Output is correct