제출 #58465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58465		Benq	관광지 (IZhO14_shymbulak)	C++14	0 / 100	936 ms	263168 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; 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.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};
}

deque<pair<pi,queue<int>>> d;

vpi CYC;
    
void ins(int x) {
    pi des = {CYC[x%sz(cyc)].f-x,CYC[x%sz(cyc)].s};
    while (sz(d) && d.back().f.f < des.f) d.pop_back();
    if (!sz(d) || d.back().f.f > des.f) d.pb({{des.f,0},queue<int>()});
    d.back().s.push(x);
    d.back().f.s += des.s;
}

void del(int x) {
    while (1) {
        if (!sz(d.front().s)) d.pop_front();
        else {
            int t = d.front().s.front();
            if (t < x) {
                d.front().f.s -= CYC[t%sz(cyc)].s;
                d.front().s.pop();
            } else break;
        }
    }
}

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 " << cyc[i%sz(cyc)] << " " << CYC[i%sz(cyc)].f << " " << d.front().f.f << " " << CYC[i%sz(cyc)].f << " " << i << "\n";
            ad(d.front().f.f+i+CYC[i%sz(cyc)].f,(ll)d.front().f.s*CYC[i%sz(cyc)].s);
            // cout << "OOPS " << (ll)d.front().f.s << " " << CYC[i%sz(cyc)].s << "\n";
            // cout << "AH " << ans.f << " " << ans.s << "\n";
        }
        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: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50