Submission #638094

#	Time	Username	Problem	Language	Result	Execution time	Memory
638094		KiriLL1ca	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	88 ms	25456 KiB

shymbulak

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#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;
#define int long long
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, bs;
        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]));
                        int n = 0;
                        for (int i = 1; i < sz(gr[v]); ++i) {
                                if (gr[v][i].fr == gr[v][1].fr) ++n;
                                else break;
                        }
                        if (gr[v][0].fr == gr[v][1].fr) ans += (n + 1ll) * 1ll * (n) / 2 * 1ll * gr[v][0].sc * 1ll * gr[v][0].sc;
                        else ans += gr[v][0].sc * 1ll * n * 1ll * gr[v][1].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;
        }

//        for (int i = 0; i < n; ++i) {
//                cout << i + 1 << ": ";
//                for (auto x : gr[i]) {
//                        cout << "{" << x.fr << ", " << x.sc << "} ";
//                } cout << endl;
//        }

        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;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50