oj.uz

답안 #171488

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171488 2019-12-28T18:42:49 Z VEGAnn 관광지 (IZhO14_shymbulak) C++14
100 / 100
 152 ms 20088 KB 
#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.0 / 30.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5256 KB Output is correct
2 Correct 6 ms 5084 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 8 ms 5496 KB Output is correct
7 Correct 9 ms 5440 KB Output is correct
8 Correct 8 ms 5496 KB Output is correct
9 Correct 8 ms 5496 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 10872 KB Output is correct
2 Correct 59 ms 11512 KB Output is correct
3 Correct 144 ms 18780 KB Output is correct
4 Correct 48 ms 11896 KB Output is correct
5 Correct 48 ms 11896 KB Output is correct
6 Correct 152 ms 16572 KB Output is correct
7 Correct 105 ms 14316 KB Output is correct
8 Correct 92 ms 18684 KB Output is correct
9 Correct 98 ms 18164 KB Output is correct
10 Correct 100 ms 20088 KB Output is correct
11 Correct 108 ms 17896 KB Output is correct
12 Correct 115 ms 18536 KB Output is correct