oj.uz

Submission #217761

# Submission time Handle Problem Language Result Execution time Memory
217761 2020-03-30T16:50:42 Z VEGAnn Mag (COCI16_mag) C++14
120 / 120
 537 ms 150904 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int, int>
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
using namespace std;
typedef long double ld;
typedef long long ll;
const int N = 1000100;
const ll OO = 1e18;
const int oo = 2e9;
vector<int> g[N];
int n, mn, a[N], ansp, ansq, mx[N], mx1[N], mx2[N];

bool smaller(int p, int q){
    return ll(p) * ll(ansq) < ll(ansp) * ll(q);
}

void dfs(int v, int p){
    mx1[v] = mx2[v] = 0;
    for (int u : g[v]){
        if (u == p) continue;
        dfs(u, v);
        if (mx1[v] < mx[u]){
            mx2[v] = mx1[v];
            mx1[v] = mx[u];
        } else if (mx2[v] < mx[u])
            mx2[v] = mx[u];
    }
    if (a[v] == 1)
        mx[v] = mx1[v] + 1;
    else mx[v] = 0;
}

void DFS(int v, int p, int cr){
    for (int u : g[v]){
        if (u == p) continue;
        int Cr = 0;
        if (a[v] == 1) {
            if (mx[u] == mx1[v])
                Cr = max(cr + 1, mx2[v] + 1);
            else Cr = max(cr + 1, mx1[v] + 1);
        }
        DFS(u, v, Cr);
    }
    int Mx1 = mx1[v], Mx2 = mx2[v];
    if (Mx1 < cr){
        Mx2 = Mx1;
        Mx1 = cr;
    } else if (Mx2 < cr)
        Mx2 = cr;
    if (smaller(a[v], Mx1 + Mx2 + 1)){
        ansp = a[v];
        ansq = Mx1 + Mx2 + 1;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    cin >> n;
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    mn = oo;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        mn = min(mn, a[i]);
    }
    if (mn > 1){
        cout << mn << "/1";
        return 0;
    }
    ansp = ansq = 1;
    dfs(0, -1);
    DFS(0, -1, 0);
    int gc = __gcd(ansp, ansq);
    cout << ansp / gc << "/" << ansq / gc << '\n';
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 18 ms 23936 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 100344 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 532 ms 147792 KB Output is correct

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 85936 KB Output is correct
2 Correct 335 ms 69552 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 88924 KB Output is correct
2 Correct 90 ms 30328 KB Output is correct
3 Correct 522 ms 150904 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 30072 KB Output is correct
2 Correct 462 ms 86264 KB Output is correct
3 Correct 332 ms 55544 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 83180 KB Output is correct
2 Correct 449 ms 87032 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 86648 KB Output is correct
2 Correct 333 ms 55416 KB Output is correct