제출 #96232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96232		Kastanda	관광지 (IZhO14_shymbulak)	C++11	100 / 100	160 ms	18516 KiB

shymbulak

#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 200005;
int n, rev[N], P[N], M[N];
int mxd[N], cnt[N];
int counter[N * 2];
int diam;    /* Answer */
ll cnt_diam; /* Answer */
pair < int , int > vcu;
vector < int > Adj[N], cyc;
int DFS_cyc(int v, int p)
{
    M[v] = 1; P[v] = p;
    for (int &u : Adj[v])
        if (u != p)
        {
            if (M[u] == 0)
                DFS_cyc(u, v);
            else if (M[u] == 1)
                vcu.first = v, vcu.second = u;
        }
    M[v] = 2;
}
void DFS(int v, int p)
{
    int xd[2] = {0, -N};
    int xc[2] = {0, 0};
    for (int &u : Adj[v])
        if (u != p && !rev[u])
        {
            DFS(u, v);
            if (xd[1] < mxd[u] + 1)
                xd[1] = mxd[u] + 1;
            if (xd[0] < xd[1])
                swap(xd[0], xd[1]);
        }
    ll tot = 0;
    for (int &u : Adj[v])
        if (u != p && !rev[u])
        {
            if (xd[1] == mxd[u] + 1)
                xc[1] += cnt[u];
            if (xd[0] == mxd[u] + 1)
            {
                xc[0] += cnt[u];
                if (xd[0] == xd[1])
                    tot -= 1LL * cnt[u] * cnt[u];
            }
        }
    if (xd[0] == 0) xc[0] ++;
    if (xd[1] == 0) xc[1] ++;

    tot += 1LL * xc[0] * xc[1];

    if (xd[0] == xd[1])
        tot >>= 1;

    mxd[v] = xd[0];
    cnt[v] = xc[0];

    if (diam < xd[0] + xd[1])
        diam = xd[0] + xd[1], cnt_diam = 0;
    if (diam == xd[0] + xd[1])
        cnt_diam += tot;
}
multiset < int > SS;
inline void Add(int i)
{
    SS.insert(mxd[cyc[i]] - i);
    counter[mxd[cyc[i]] - i + N] += cnt[cyc[i]];
}
inline void Del(int i)
{
    counter[mxd[cyc[i]] - i + N] -= cnt[cyc[i]];
    auto it = SS.lower_bound(mxd[cyc[i]] - i);
    assert(it != SS.end() && (*it) == (mxd[cyc[i]] - i));
    SS.erase(it);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        Adj[v].pb(u);
        Adj[u].pb(v);
    }
    /* Building the main cycle ... */

    vcu = {-1, -1};
    DFS_cyc(1, 0);
    assert(vcu.first != -1);
    assert(vcu.second != -1);
    while (vcu.first != P[vcu.second])
    {
        cyc.pb(vcu.first);
        rev[vcu.first] = (int)cyc.size();
        vcu.first = P[vcu.first];
    }

    /* End of :: Building the main cycle ... */

    /* finding diameter of the trees ... */

    for (int i = 0; i < (int)cyc.size(); i++)
        DFS(cyc[i], 0);

    /* End of :: finding diameter of the trees ... */

    /* Everything else ... */

    int m = (int)cyc.size();
    for (int i = 0; i < m; i++)
        cyc.pb(cyc[i]);

    for (int i = 0; i < (m >> 1); i++)
        Add(i);

    vector < int > mark(N, 0);
    for (int i = (m >> 1); i < (int)cyc.size(); i++)
    {
        if (mark[cyc[i]])
            break;
        mark[cyc[i]] = 1;

        if (diam < mxd[cyc[i]] + i + (*SS.rbegin()))
            diam = mxd[cyc[i]] + i + (*SS.rbegin()), cnt_diam = 0;
        if (diam == mxd[cyc[i]] + i + (*SS.rbegin()))
            cnt_diam += 1LL * cnt[cyc[i]] * counter[(*SS.rbegin()) + N];

        Del(i - (m >> 1));
        Add(i);
    }
    return !printf("%lld\n", cnt_diam);
}

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

shymbulak.cpp: In function 'int DFS_cyc(int, int)':
shymbulak.cpp:27:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
shymbulak.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &u);
         ~~~~~^~~~~~~~~~~~~~~~

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