oj.uz

Submission #416223

# Submission time Handle Problem Language Result Execution time Memory
416223 2021-06-02T08:04:35 Z mewnian Mag (COCI16_mag) C++17
24 / 120
 461 ms 123040 KB 
#include <bits/stdc++.h>
#define sze(x) (ll)x.size()
#define idx(x, a) get<x>(a)
#define LID(x) (x << 1LL)
#define RID(x) (x << 1LL) + 1LL
#define ID(x) (x + MAXN)
#define CONV(x) (x - MAXN)
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pi;

const ll MAXN = 1'000'003;

ll a[MAXN], n;
vector<ll> g[MAXN];
ll res1, res2 = 0;

ll dfs(ll u, ll p = -1)
{
    ll mx1 = 0, mx2 = 0;
    for (ll v : g[u])
    {
        if (v == p) continue;
        ll childr = dfs(v, u);
        if (childr > mx1) tie(mx1, mx2) = make_pair(childr, mx1);
        else if (childr > mx2) mx2 = childr;
    }
    if (a[u] != 1)
    {
        res2 = max(res2, mx1);
        return 0;
    }
    else
    {
        res2 = max({res2, mx1 + 1, mx1 + mx2 + 1});
        return mx1 + 1;
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cout.tie(0);
    #ifdef OFFLINE
    freopen("input.inp", "r", stdin);
    #endif
    cin >> n;
    for (ll i = 1; i < n; ++i)
    {
        ll u, v; cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }
    for (ll i = 1; i <= n; ++i) cin >> a[i];
    res1 = *min_element(a + 1, a + n + 1);
    dfs(1);
    if (res2 != 0) cout << "1/" << res2;
    else cout << res1 << "/1";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 376 ms 80140 KB Output isn't correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 461 ms 123040 KB Output isn't correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 433 ms 62684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 397 ms 65256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 28320 KB Output is correct
2 Incorrect 412 ms 78392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 60816 KB Output is correct
2 Incorrect 413 ms 62160 KB Output isn't correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 63376 KB Output is correct
2 Correct 365 ms 46400 KB Output is correct