Submission #416223

#	Time	Username	Problem	Language	Result	Execution time	Memory
416223		mewnian	Mag (COCI16_mag)	C++17	24 / 120	461 ms	123040 KiB

mag

#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 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 12 / 12