제출 #58471

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

shymbulak

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 200001;

int N, p[MX];
vi adj[MX];
bitset<MX> vis, incyc;
pi des = {-1,-1};
pl ans = {0,0};
vi cyc;

void ad(int x, ll y) {
    if (ans.f < x) ans = {x,0};
    if (ans.f == x) ans.s += y;
}

void dfs(int a, int b = 0) {
    p[a] = b; vis[a] = 1;
    for (int i: adj[a]) if (i != p[a]) {
        if (vis[i]) {
            des = {a,i};
            break;
        }
        dfs(i,a);
        if (des != mp(-1,-1)) break;
    }
}

void init() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    F0R(i,N) {
        /*int a,b; // int a = i+1,b = (i+1)%N+1; 
        if (i == 0) {
            a = N;
            b = rand() % (N-1)+1;
        } else {
            a = i+1;
            b = rand() % i +1;
        }*/
        int a,b; cin >> a >> b;
        adj[a].pb(b), adj[b].pb(a);
    }
    dfs(1);
    while (des.f != des.s) cyc.pb(des.f), des.f = p[des.f];
    cyc.pb(des.s);
    for (int i: cyc) incyc[i] = 1;
}

pi dfs2(int a, int b = 0) {
    vpi v;
    for (int i: adj[a]) if (i != b && !incyc[i]) {
        auto A = dfs2(i,a); A.f ++;
        v.pb(A);
    }
    v.pb({0,1});
    sort(all(v)); reverse(all(v));
    int ind = 0, tot = 0;
    while (ind < sz(v) && v[ind].f == v[0].f) tot += v[ind++].s;
    if (ind == 1) {
        int ind2 = 1;
        ll tot2 = 0;
        while (ind2 < sz(v) && v[ind2].f == v[1].f) tot2 += v[ind2++].s;
        if (sz(v) > 1) ad(v[0].f+v[1].f,(ll)tot2*tot);
    } else {
        ll TOT = (ll)tot*(tot-1)/2;
        F0R(i,ind) TOT -= (ll)v[i].s*(v[i].s-1)/2;
        ad(2*v[0].f,TOT);
    }
    return {v[0].f,tot};
}

vpi CYC;

int getSum(int x) {
    return CYC[x%sz(cyc)].s;
}

pi csum = {MOD,0};
deque<pi> d;

void pb(pi x) {
    d.pb(x);
    if (csum.f == MOD) csum.f = x.f;
    if (csum.f == x.f) csum.s += getSum(x.s);
}

void pop_back() {
    if (d.back().f == csum.f) {
        csum.s -= getSum(d.back().s);
        if (csum.s == 0) csum = {MOD,0};
    }
    d.pop_back();
}

void pop_front() {
    if (d.front().f == csum.f) {
        csum.s -= getSum(d.front().s);
        if (csum.s == 0) csum = {MOD,0};
    }
    d.pop_front();
}

void ins(int x) {
    pi des = {CYC[x%sz(cyc)].f-x,x};
    while (sz(d) && d.back().f < des.f) pop_back();
    pb(des);
}

void del(int x) {
    while (d.front().s < x) {
        pop_front();
        if (csum.f == MOD) {
            csum = {d.front().f,0};
            stack<pi> tmp;
            while (sz(d) && d.front().f == csum.f) {
                csum.s += getSum(d.front().s);
                tmp.push(d.front()); d.pop_front();
            }
            while (sz(tmp)) {
                d.push_front(tmp.top());
                tmp.pop();
            }
        }
    }
}

int main() {
    init();
    for (int i: cyc) CYC.pb(dfs2(i));
    
    int t = sz(cyc)/2;
    
    F0R(i,2*sz(cyc)) {
        if (i >= t && i < sz(cyc)+t) {
            del(i-t);
            //cout << "OH " << sz(d) << " " << d.front().s << "\n";
            //cout << cyc[i%sz(cyc)] << " " << csum.f << " " << i << " " << getSum(i) << "\n";
            ad(csum.f+i+CYC[i%sz(cyc)].f,(ll)csum.s*getSum(i));
        }
        ins(i);
    }
    cout << ans.s;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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