oj.uz

Submission #416218

# Submission time Handle Problem Language Result Execution time Memory
416218 2021-06-02T08:00:06 Z mewnian Mag (COCI16_mag) C++17
12 / 120
 481 ms 140020 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});
        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 16 ms 23756 KB Output is correct
2 Correct 16 ms 23800 KB Output is correct

Subtask #2
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 #3
0 / 12.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 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 481 ms 140020 KB Output isn't correct

Subtask #6
0 / 12.0

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

Subtask #7
0 / 12.0

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

Subtask #8
0 / 12.0

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

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 76540 KB Output is correct
2 Incorrect 421 ms 79216 KB Output isn't correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 78800 KB Output is correct
2 Incorrect 381 ms 54028 KB Output isn't correct