Submission #638103

# Submission time Handle Problem Language Result Execution time Memory
638103 2022-09-04T15:24:12 Z KiriLL1ca Shymbulak (IZhO14_shymbulak) C++14
70 / 100
202 ms 40132 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'

using namespace std;
using namespace __gnu_pbds;



typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 10;
vector <int> g[N];
vector <pii> gr[N];
pii val[N], two[N];
ll ans = 0;
int used[N], par[N], vis[N], mx[N], c[N], h[N];
int diam = 0;
vector <int> cyc;

inline bool find_cyc (int v, int p) {
        used[v] = 1;
        for (auto u : g[v]) {
                if (u == p || used[u] == 2) continue;
                if (!used[u]) {
                        par[u] = v;
                        if (find_cyc(u, v)) return 1;
                }
                else {
                        int c = v; cyc.pb(u);
                        while (c != u) cyc.pb(c), c = par[c];
                        return 1;
                }
        }
        used[v] = 2; return 0;
}

int mxh, cnt;
inline void calc (int v) {
        used[v] = 1; umax(mxh, h[v]);
        pii p = {0, 0}, bs = {0, 0};
        for (auto u : g[v]) {
                if (used[u]) continue;
                h[u] = h[v] + 1; calc(u);

                map <int, int> mp;
                for (auto x : gr[u]) mp[-x.fr] += x.sc;
                pii it = *mp.begin(); it.fr = -it.fr; ++it.fr;
                gr[v].pb(it);

                if (val[u].fr + 1 > p.fr) {
                        swap(p.fr, p.sc); p.fr = val[u].fr + 1;
                        bs = val[u]; ++bs.fr;
                }
                else {
                        if (val[u].fr + 1 == p.fr) ++bs.sc;
                        umax(p.sc, val[u].fr + 1);
                }
        }

        val[v] = bs; two[v] = p;
        if (!sz(gr[v])) gr[v].pb({0, 1});
        umax(diam, p.fr + p.sc);
}
inline void gogo (int v) {
        vis[v] = 1; cnt += (h[v] == mxh);
        for (auto u : g[v]) if (!vis[u]) gogo(u);
}
inline void dfs (int v) {
        used[v] = 1;
        if (two[v].fr + two[v].sc == diam) {
                if (sz(gr[v]) == 1) ans += gr[v][0].sc;
                else {
                        sort(rall(gr[v]));
                        if (gr[v][0].fr == gr[v][1].fr) {
                                ll s = 0;
                                for (int i = 0; i < sz(gr[v]); ++i) {
                                        if (gr[v][0].fr != gr[v][i].fr) break;
                                        ans += gr[v][i].sc * s;
                                        s += gr[v][i].sc;
                                }
                        }
                        else {
                                for (int i = 1; i < sz(gr[v]); ++i) {
                                        if (gr[v][1].fr != gr[v][i].fr) break;
                                        ans += gr[v][0].sc * gr[v][i].sc;
                                }
                        }
                }
        }
        for (auto u : g[v]) if (!used[u]) dfs(u);
}

inline void solve () {
        int n; cin >> n;
        for (int i = 0; i < n; ++i) {
                int u, v; cin >> u >> v; --u, --v;
                g[u].pb(v); g[v].pb(u);
        }
        find_cyc(0, -1); fill(used, used + N, 0);
        for (auto v : cyc) used[v] = vis[v] = 1;
        int uk = 1;
        for (auto i : cyc) {
                mxh = cnt = 0;
                calc(i); gogo(i);
                mx[uk] = mxh; c[uk] = cnt; ++uk;
        }

        int half = sz(cyc) / 2;
        map <int, ll> mlef, mrig;
        multiset <int> slef, srig;

        for (int i = 1; i <= sz(cyc); ++i) {
                if (sz(srig)) umax(diam,           i + mx[i] + *srig.rbegin());
                if (sz(slef)) umax(diam, sz(cyc) - i + mx[i] + *slef.rbegin());

                srig.insert(mx[i] - i);
                if (i >= half + 1) {
                        slef.insert(mx[i - half] - i + half);
                        srig.erase(srig.find(mx[i - half] - i + half));
                }
        }

        for (int i = 1; i <= sz(cyc); ++i) {
                ans += c[i] * 1ll * (mrig[diam - mx[i] - i] + mlef[diam - sz(cyc) + i - mx[i]]);
                mrig[mx[i] - i] += c[i];
                if (i >= half + 1) {
                        mlef[mx[i - half] + i - half] += c[i - half];
                        mrig[mx[i - half] - i + half] -= c[i - half];
                }

                if (half * 2 == sz(cyc) && i >= half + 1 && mx[i] + half + mx[i - half] == diam) ans += c[i] * 1ll * c[i - half];
        }

        fill(used, used + N, 0); for (auto i : cyc) used[i] = 1;
        for (auto x : cyc) dfs(x);

        cout << ans << endl;
}
signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        int t = 1; //cin >> t;
        while (t--) solve();
        return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 5 ms 11220 KB Output is correct
3 Correct 5 ms 11288 KB Output is correct
4 Incorrect 5 ms 11220 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 11604 KB Output is correct
2 Correct 7 ms 11388 KB Output is correct
3 Correct 6 ms 11476 KB Output is correct
4 Correct 6 ms 11472 KB Output is correct
5 Correct 9 ms 11988 KB Output is correct
6 Correct 10 ms 11988 KB Output is correct
7 Correct 9 ms 12012 KB Output is correct
8 Correct 8 ms 11952 KB Output is correct
9 Correct 8 ms 11988 KB Output is correct
10 Correct 8 ms 11988 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 86 ms 23568 KB Output is correct
2 Correct 106 ms 25412 KB Output is correct
3 Correct 75 ms 35140 KB Output is correct
4 Correct 57 ms 24340 KB Output is correct
5 Correct 59 ms 24268 KB Output is correct
6 Correct 202 ms 35232 KB Output is correct
7 Correct 158 ms 31164 KB Output is correct
8 Correct 110 ms 37020 KB Output is correct
9 Correct 113 ms 36796 KB Output is correct
10 Correct 101 ms 40132 KB Output is correct
11 Correct 129 ms 38060 KB Output is correct
12 Correct 149 ms 39444 KB Output is correct