제출 #319388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319388		Trickster	관광지 (IZhO14_shymbulak)	C++14	0 / 100	228 ms	35064 KiB

shymbulak

//Suleyman Atayew
 
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
 
#define N 200010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mod 1000000007
#define pii pair <ll, ll>
#define sz(a) (ll)(a.size())
ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; }

using namespace std;

ll n, a, b, sz;
map <pii, ll> M;
ll vis[N], L[N*4];
pii p[N], H[N][5], S[N*4];
vector <ll> E[N], arr, v, T[N];

void dfs(ll nd, ll pr)
{
    arr.pb(nd);
    vis[nd] = vis[pr]+1;

    for(auto i: E[nd]) {
        if(i == pr) continue;

        if(vis[i]) {
            for(ll h = vis[i]-1; h < vis[nd]; h++) v.pb(arr[h]);
            return;
        }

        dfs(i, nd);

        if(!v.empty()) return;
    }
    arr.pop_back();
    vis[nd] = 0;
}

void dfs2(ll nd)
{
    vis[nd] = 1;

    for(auto i: T[nd]) {
        if(vis[i]) continue;

        dfs2(i);

        if(H[nd][0].ff < H[i][0].ff) H[nd][1] = H[nd][0], H[nd][0] = {H[i][0].ff, 0};
        if(H[nd][0].ff == H[i][0].ff) H[nd][0].ss += H[i][0].ss;
        else {
            if(H[nd][1].ff < H[i][0].ff) H[nd][1] = {H[i][0].ff, 0};

            if(H[nd][1].ff == H[i][0].ff) H[nd][1].ss += H[i][0].ss;
        }
    }

    H[nd][0] = {H[nd][0].ff+1, max(1LL, H[nd][0].ss)};
    H[nd][1] = {H[nd][1].ff+1, max(1LL, H[nd][1].ss)};
}

void com(ll node) {
    if(S[node*2].ff < S[node*2+1].ff) S[node] = S[node*2+1];
    if(S[node*2].ff > S[node*2+1].ff) S[node] = S[node*2];
    if(S[node*2].ff == S[node*2+1].ff) S[node] = {S[node*2].ff, S[node*2].ss + S[node*2+1].ss};    
}

void build(ll l, ll r, ll node)
{
    if(l == r) {
        S[node] = p[l];
        return;
    }

    build(l, (l+r)/2, node*2);
    build((l+r)/2+1, r, node*2+1);

    com(node);
}
void shift(ll node, ll to)
{
    L[to] += L[node];
    S[to].ff += L[node];
}
void upd(ll a, ll b, ll x, ll l, ll r, ll node)
{
    if(l > b || r < a) return;

    if(l >= a && r <= b) {
        S[node].ff += x;
        L[node] += x;
        return;
    }

    shift(node, node*2);
    shift(node, node*2+1);
    L[node] = 0;

    upd(a, b, x, l, (l+r)/2, node*2);
    upd(a, b, x, (l+r)/2+1, r, node*2+1);

    com(node);
}
void upd2(ll pos, double x, ll l, ll r, ll node)
{
    if(l == r) {
        S[node].ss *= x;
        return;
    }

    shift(node, node*2);
    shift(node, node*2+1);
    L[node] = 0;

    if(pos <= (l+r)/2)
        upd2(pos, x, l, (l+r)/2, node*2);
    else
        upd2(pos, x, (l+r)/2+1, r, node*2+1);

    com(node);
}
pii upd3(ll pos, pii x, ll l, ll r, ll node)
{
    if(l == r) {
        pii a = S[node];
        S[node] = x;
        return a;
    }

    shift(node, node*2);
    shift(node, node*2+1);
    L[node] = 0;

    pii ret;

    if(pos <= (l+r)/2) 
        ret = upd3(pos, x, l, (l+r)/2, node*2);
    else
        ret = upd3(pos, x, (l+r)/2+1, r, node*2+1);
    
    com(node);

    return ret;
}
void job(ll l, ll r, ll x)
{
    if(r > sz) r -= sz;
    if(l > sz) l -= sz;

    if(r >= l) upd(l, r, x, 1, sz, 1);
    else {
        upd(l, sz, x, 1, sz, 1);
        upd(1, r, x, 1, sz, 1);
    }
}

int main()
{
    cin >> n;

    for(ll i = 1; i <= n; i++) {
        cin >> a >> b;

        E[a].pb(b);
        E[b].pb(a);
        p[i] = {a, b};
    }

    dfs(1, 0);
    
    sz = v.size();

    M[{v[0], v.back()}] = M[{v.back(), v[0]}] = 1;
    for(ll i = 1; i < v.size(); i++) M[{v[i], v[i-1]}] = M[{v[i-1], v[i]}] = 1;
    
    for(ll i = 1; i <= n; i++) {
        if(M[p[i]]) continue;

        T[p[i].ff].pb(p[i].ss);
        T[p[i].ss].pb(p[i].ff);
    }

    memset(vis, 0, sizeof(vis));
    for(auto i: v) dfs2(i);

    for(ll i = 1; i <= sz; i++) p[i] = H[v[i-1]][0];

    for(ll i = 2, h = sz; i < h; i++, h--) p[i].ff += i-1, p[h].ff += i-1;
    if(sz%2 == 0) p[sz/2+1].ff += sz/2;

    build(1, sz, 1);

    ll l = 2, lm = (sz-1)/2, pos = -1, last = -1, mx = 0, ans = 0;

    if(sz%2 == 0) pos = sz/2+1;
    for(ll i = 1; i <= sz; i++) {
        pii cur = upd3(i, {0, 0}, 1, sz, 1);
        
        if(last != -1) upd2(last, 0.5, 1, sz, 1);
        if(pos != -1) upd2(pos, 2, 1, sz, 1);

        ll now = S[1].ff + H[v[i-1]][0].ff - 1;
        ll cnt = S[1].ss * H[v[i-1]][0].ss;

        if(mx < now) {
            mx = now;
            ans = 0;
        }
        if(mx == now) ans += cnt;

        upd3(i, cur, 1, sz, 1);

        job(l, l+lm, -1);
        job(sz-lm+i, i, 1);
        l++;

        if(pos == -1) continue;

        last = pos, pos++;

        if(pos > sz) pos -= sz;
    }

    for(auto i: v) {
        ll now = 0, cnt = 2, ok = 0;

        for(auto h: T[i])
            if(H[h][0].ff == H[i][0].ff - 1) {
                ok ++;
                cnt *= H[h][0].ss;
            }

        if(ok <= 1) {
            now = H[i][1].ff + H[i][0].ff - 1;
            cnt = H[i][1].ss * H[i][0].ss * 2;
        } else {
            now = H[i][0].ff * 2 - 1;
        }

        if(mx < now) {
            mx = now;
            ans = 0;
        }
        if(mx == now) ans += cnt;
    }

    cout << ans/2;
}
/*
6
1 2
1 3
2 4
4 3
4 5
4 6
------------------------- 4
4
1 2
1 3
1 4
4 3
------------------------- 2
9
1 2
1 3
2 3
3 4
4 5
5 6
3 7
7 8
8 9
------------------------ 1
8
1 2
3 4
5 6
7 8
2 4
4 7
7 5
5 2
----------------------- 4
7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
---------------------- 7
12
1 3
2 3
7 4
8 4
9 5
10 5
12 6
11 6
3 4
4 5
5 6
6 3
--------------------- 16
*/

컴파일 시 표준 에러 (stderr) 메시지

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:186:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for(ll i = 1; i < v.size(); i++) M[{v[i], v[i-1]}] = M[{v[i-1], v[i]}] = 1;
      |                   ~~^~~~~~~~~~

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