oj.uz

Submission #24335

# Submission time Handle Problem Language Result Execution time Memory
24335 2017-06-05T15:29:04 Z szawinis Mag (COCI16_mag) C++14
84 / 120
 619 ms 262144 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33432 KB Output is correct
2 Correct 3 ms 33432 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33432 KB Output is correct
2 Correct 3 ms 33432 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 152000 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33432 KB Output is correct
2 Memory limit exceeded 516 ms 262144 KB Memory limit exceeded

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 463 ms 262144 KB Memory limit exceeded

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 64512 KB Output is correct
2 Correct 353 ms 56864 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 66372 KB Output is correct
2 Correct 99 ms 36600 KB Output is correct
3 Memory limit exceeded 443 ms 262144 KB Memory limit exceeded

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 36600 KB Output is correct
2 Correct 536 ms 66596 KB Output is correct
3 Correct 619 ms 49536 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 65860 KB Output is correct
2 Correct 553 ms 64056 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 66236 KB Output is correct
2 Correct 583 ms 49536 KB Output is correct