Submission #24335

#	Time	Username	Problem	Language	Result	Execution time	Memory
24335		szawinis	Mag (COCI16_mag)	C++14	84 / 120	619 ms	262144 KiB

mag

#include <bits/stdc++.h>
using namespace std;
const int MAX = (1e6)+1, INF = (1e9)+10;

int n, ans = INF, len = 1, x[MAX], dp[MAX];
vector<int> g[MAX];
inline bool opt(int p, int q) {
    return 1ll*p*len < 1ll*q*ans;
}
void calc(int u, int p) {
    int mx = 0;
    for(int v: g[u]) if(v != p) calc(v, u), mx = max(dp[v], mx);
    dp[u] = (x[u] == 1)*(mx+1);
}
void dfs(int u, int p, int lp) {
    if(opt(x[u], lp+1)) ans = x[u], len = 1;
    set<pair<int,int> > mx;
    for(int v: g[u]) if(v != p) {
        mx.emplace(dp[v], v);
        if(mx.size() > 2) mx.erase(mx.begin());
    }
    for(int v: g[u]) if(v != p) {
        int nlp = lp;
        if(!mx.empty()) {
            if(mx.rbegin()->second != v) nlp = max(mx.rbegin()->first, nlp);
            else if(mx.size() > 1) nlp = max(mx.begin()->first, nlp);
        }
        if(opt(x[u], nlp+dp[v]+1)) ans = x[u], len = nlp+dp[v]+1;
        dfs(v, u, (x[u] == 1)*(nlp+1));
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) cin >> x[i];
    calc(1, 0);
    dfs(1, 0, 0);
    int tmp = __gcd(ans, len);
    ans /= tmp;
    len /= tmp;
    cout << ans << '/' << len;
}

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