oj.uz

답안 #106569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106569 2019-04-19T06:28:25 Z Frankenween 관광지 (IZhO14_shymbulak) C++17
100 / 100
 232 ms 23900 KB 
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#define ull unsigned long long
#define pll pair<ll, ll>
#define mp make_pair
#define ll long long
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define ld long double
const ll mod = (ll)1e9 + 7;
const ll BASE = 47;
const ll inf = (ll)1e18;
const long double e = 2.718281828459;
const long double pi = 3.141592653;
const ld EPS = 1e-9;


using namespace std;


template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};


void solve() {
    ll n;
    cin >> n;
    vector<vector<ll>> g(n);
    for (int i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    vector<ll> cycle;
    vector<bool> on_cyc(n), used(n);

    function<ll(ll, ll)> dfs = [&](ll v, ll pr) {
        used[v] = true;
        for (auto u : g[v]) {
            if (u == pr) {
                continue;
            }
            if (used[u]) {
                cycle.pb(v);
                on_cyc[v] = true;
                return u;
            }
            ll res = dfs(u, v);
            if (res == -1) {
                continue;
            }
            if (res == -2) {
                return -2LL;
            }
            cycle.pb(v);
            on_cyc[v] = true;
            if (res == v) {
                res = -2;
            }
            return res;
        }
        return -1LL;
    };
    dfs(0, -1);

    vector<ll> cnt(n), diam(n + 1), h(n + 1), max_h_val(n);

    function<void(ll, ll)> dfs1 = [&](ll v, ll pr) {
        h[v] = 0;
        ll mx1 = 0, mx2 = 0, sum_variants = 0, have_deep_children = 0;
        for (auto u : g[v]) {
            if (u == pr or on_cyc[u]) {
                continue;
            }
            dfs1(u, v);
            h[v] = max(h[v], h[u] + 1);
            if (mx1 < h[u] + 1) {
                sum_variants = max_h_val[u];
                have_deep_children = 1;
                mx2 = mx1;
                mx1 = h[u] + 1;
            } else if (mx1 == h[u] + 1) {
                sum_variants += max_h_val[u];
                have_deep_children++;
            } else if (mx2 < h[u] + 1) {
                mx2 = h[u] + 1;
            }
        }
        max_h_val[v] = max(1LL, sum_variants);
        if (have_deep_children > 1) {
            diam[v] = mx1 * 2;
            ll sum = 0, sq = 0;
            for (auto u : g[v]) {
                if (u == pr or on_cyc[u] or h[u] + 1 != mx1) {
                    continue;
                }
                sum += max_h_val[u];
                sq += max_h_val[u] * max_h_val[u];
            }
            cnt[v] = (sum * sum - sq) / 2;
        } else {
            diam[v] = mx1 + mx2;
            for (auto u : g[v]) {
                if (u == pr or on_cyc[u] or h[u] + 1 != mx2) {
                    continue;
                }
                cnt[v] += max_h_val[v] * max_h_val[u];
            }
        }

    };

    for (auto v : cycle) {
        dfs1(v, -1);
    }
    map<ll, ll> pph;
    ll len = cycle.size();
    for (int i = 1; i <= len / 2; i++) {
        pph[-(h[cycle[i]] + i)] += max_h_val[cycle[i]];
    }
    vector<ll> answer(n + 1);
    for (int i = 0; i < len; i++) {
        auto value = *pph.begin();
        ll upd_len = -value.first - i + h[cycle[i]];
        answer[upd_len] += value.second * max_h_val[cycle[i]];
        pph[-(h[cycle[(i + 1) % len]] + i + 1)] -= max_h_val[cycle[(i + 1) % len]];
        if (pph[-(h[cycle[(i + 1) % len]] + i + 1)] == 0) {
            pph.erase(-(h[cycle[(i + 1) % len]] + i + 1));
        }
        pph[-(h[cycle[(i + 1 + len / 2) % len]] + i + 1 + len / 2)] += max_h_val[cycle[(i + 1 + len / 2) % len]];
    }
    for (int i = 0; i < n; i++) {
        answer[diam[i]] += cnt[i];
    }
    ll i = n;
    while (answer[i] == 0) {
        i--;
    }
    cout << answer[i];
}


int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout.precision(30);
    ll seed = time(0);
    //cerr << "Seed: " << seed << "\n";
    srand(seed);
    solve();
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 6 ms 996 KB Output is correct
8 Correct 4 ms 896 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 5 ms 896 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 11512 KB Output is correct
2 Correct 99 ms 11880 KB Output is correct
3 Correct 65 ms 17648 KB Output is correct
4 Correct 46 ms 11512 KB Output is correct
5 Correct 54 ms 11604 KB Output is correct
6 Correct 207 ms 21752 KB Output is correct
7 Correct 156 ms 16504 KB Output is correct
8 Correct 114 ms 22680 KB Output is correct
9 Correct 112 ms 23000 KB Output is correct
10 Correct 93 ms 23900 KB Output is correct
11 Correct 232 ms 22244 KB Output is correct
12 Correct 187 ms 23276 KB Output is correct