oj.uz

답안 #96229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96229 2019-02-07T11:10:26 Z Kastanda 관광지 (IZhO14_shymbulak) C++11
0 / 100
 198 ms 17036 KB 
#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];

    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);
}

Compilation message

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:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
shymbulak.cpp:86: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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5880 KB Output is correct
2 Incorrect 6 ms 5880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Incorrect 7 ms 5880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 10488 KB Output is correct
2 Correct 63 ms 10872 KB Output is correct
3 Correct 59 ms 15264 KB Output is correct
4 Correct 46 ms 11128 KB Output is correct
5 Correct 51 ms 11088 KB Output is correct
6 Correct 198 ms 14508 KB Output is correct
7 Correct 120 ms 12940 KB Output is correct
8 Correct 99 ms 16120 KB Output is correct
9 Correct 144 ms 16052 KB Output is correct
10 Correct 92 ms 17036 KB Output is correct
11 Incorrect 98 ms 15584 KB Output isn't correct
12 Halted 0 ms 0 KB -