제출 #171488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171488		VEGAnn	관광지 (IZhO14_shymbulak)	C++14	100 / 100	152 ms	20088 KiB

shymbulak

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pll pair<ll, ll>
using namespace std;
typedef long long ll;
const ll OO = 1e18;
const int N = 200100;
const int M = 1010;
const int big = 1e8;
//const int PW = (1 << N);
vector<int> vc, g[N], cyc;
int mrk[N], n, mx1[N], mx2[N], kl1[N], kl2[N], ans = -1, m, mm, pos[N];
ll st[4 * N], psh[4 * N];
ll kans = 0, kol[4 * N];
bool in_cyc[N];

void CYCLE(int lst){
    cyc.clear();
    int it = sz(vc) - 1;
    while (1){
        cyc.PB(vc[it]);
        in_cyc[vc[it]] = 1;
        if (vc[it] == lst)
            break;
        it--;
    }
}

void dfs(int v, int p){
    if (sz(cyc) > 0) return;
    vc.PB(v);
    mrk[v] = 1;
    for (int u : g[v]){
        if (u == p) continue;
        if (mrk[u] == 0)
            dfs(u, v); else
        if (mrk[u] == 1)
            CYCLE(u);
    }
    mrk[v] = 2;
    vc.pop_back();
}

void calc_max(int v, int p){
    mx1[v] = 0; mx2[v] = -1;
    kl1[v] = 1; kl2[v] = 0;
    int ko = 1;
    ll res = 0, sm = 0;
    for (int u : g[v]){
        if (u == p || in_cyc[u]) continue;
        calc_max(u, v);
        if (mx1[v] == mx1[u] + 1){
            kl1[v] += kl1[u];
            ko++;
            res += sm * ll(kl1[u]);
            sm += kl1[u];
        } else if (mx1[v] < mx1[u] + 1){
            swap(kl1[v], kl2[v]);
            swap(mx1[v], mx2[v]);
            kl1[v] = kl1[u];
            ko = 1;
            res = 0;
            sm = kl1[u];
            mx1[v] = mx1[u] + 1;
        } else if (mx2[v] == mx1[u] + 1){
            kl2[v] += kl1[u];
        } else if (mx2[v] < mx1[u] + 1) {
            kl2[v] = kl1[u];
            mx2[v] = mx1[u] + 1;
        }
    }

    if (mx1[v] < 1) return;

    if (ko > 1){
        if (mx1[v] + mx1[v] > ans){
            ans = mx1[v] + mx1[v];
            kans = 0;
        }
        if (mx1[v] + mx1[v] == ans)
            kans += res * 2;
    } else {
        if (mx1[v] + mx2[v] > ans){
            ans = mx1[v] + mx2[v];
            kans = 0;
        }
        if (mx1[v] + mx2[v] == ans)
            kans += ll(kl1[v]) * ll(kl2[v]) * 2;
    }
}

void build(int v, int l, int r){
    psh[v] = 0;
    if (l == r){
        st[v] = mx1[cyc[l]] + min(l, m - l);
        kol[v] = kl1[cyc[l]];
        return;
    }
    int md = (l + r) >> 1;
    build(v + v, l, md);
    build(v + v + 1, md + 1, r);
    st[v] = max(st[v + v], st[v + v + 1]);

    kol[v] = 0;
    if (st[v] == st[v + v])
        kol[v] += kol[v + v];

    if (st[v] == st[v + v + 1])
        kol[v] += kol[v + v + 1];
}

void push(int v){
    if (psh[v] != 0){
        st[v] += psh[v];
        if (v + v + 1 < 4 * n){
            psh[v + v] += psh[v];
            psh[v + v + 1] += psh[v];
        }
        psh[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, int vl){
    push(v);
    if (l > r) return;
    if (tl == l && tr == r){
        psh[v] += vl;
        push(v);
        return;
    }
    int md = (tl + tr) >> 1;
    update(v + v, tl, md, l, min(r, md), vl);
    update(v + v + 1, md + 1, tr, max(l, md + 1), r, vl);

    st[v] = max(st[v + v], st[v + v + 1]);

    kol[v] = 0;
    if (st[v] == st[v + v])
        kol[v] += kol[v + v];

    if (st[v] == st[v + v + 1])
        kol[v] += kol[v + v + 1];
}

void upd(int l, int r, int vl){
    if (l < 0){
        update(1, 0, m - 1, 0, r, vl);
        update(1, 0, m - 1, m + l, m - 1, vl);
    } else if (r >= m){
        update(1, 0, m - 1, l, m - 1, vl);
        update(1, 0, m - 1, 0, r - m, vl);
    } else {
        update(1, 0, m - 1, l, r, vl);
    }
}

void PUSH(int v, int l, int r){
    push(v);
    if (l == r) return;
    int md = (l + r) >> 1;
    PUSH(v + v, l, md);
    PUSH(v + v + 1, md + 1, r);

    st[v] = max(st[v + v], st[v + v + 1]);

    kol[v] = 0;
    if (st[v] == st[v + v])
        kol[v] += kol[v + v];

    if (st[v] == st[v + v + 1])
        kol[v] += kol[v + v + 1];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("penguins.in","r",stdin); freopen("penguins.out","w",stdout);
//    freopen("in.txt","r",stdin);
    cin >> n;
    for (int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].PB(y);
        g[y].PB(x);
    }
    dfs(0, -1);
    for (int it = 0; it < sz(cyc); it++){
        int cr = cyc[it];
        pos[cr] = it;
        calc_max(cr, -1);
    }

    bool good = (sz(cyc) % 2 == 0);

    m = sz(cyc);
    mm = m / 2;

    build(1, 0, m - 1);

    for (int it = 0; it < m; it++){
        int v = cyc[it];
        if (it > 0){
            upd(it - mm, it - 1, +1);
            upd(it, it + mm - 1, -1);
        }

        update(1, 0, m - 1, it, it, -big);

//        PUSH(1, 0, m - 1);

        ll mdst = st[1] + mx1[v];

        if (mdst > ans){
            ans = mdst;
            kans = 0;
        }

        if (mdst == ans)
            kans += ll(kl1[v]) * kol[1];

        if (good){
            int op = cyc[(it + mm) % m];
            if (mm + mx1[op] + mx1[v] == ans)
                kans += ll(kl1[op]) * ll(kl1[v]);
        }

        update(1, 0, m - 1, it, it, +big);
    }
//    for (int i1 = 0; i1 < sz(cyc); i1++)
//    for (int i2 = i1 + 1; i2 < sz(cyc); i2++){
//        int dst = i2 - i1, n1 = cyc[i1], n2 = cyc[i2];
//        dst = min(dst, sz(cyc) - dst);
//        dst += mx1[n1] + mx1[n2];
//
//        if (dst > ans){
//            ans = dst;
//            kans = 0;
//        }
//
//        if (dst == ans)
//            kans += ll(kl1[n1]) * ll(kl1[n2]);
//
//        if (good && (i2 - i1) == (sz(cyc) >> 1) && dst == ans)
//            kans += ll(kl1[n1]) * ll(kl1[n2]);
//    }
    cout << kans / 2 << '\n';
    return 0;
}

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