Submission #139429

#	Time	Username	Problem	Language	Result	Execution time	Memory
139429		Minnakhmetov	Mag (COCI16_mag)	C++14	120 / 120	577 ms	158656 KiB

mag

#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 / 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