Submission #96227

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
96227	2019-02-07T10:41:20 Z	Kastanda	Shymbulak (IZhO14_shymbulak)	C++11	Compilation error	0 ms	0 KB

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], H[N], M[N];
int mxd[N], cnt[N];
int counter[N * 2];
int diam; /* Answer */
ll cnt_diam;   /* Answer */
vector < int > Adj[N], cyc;
int DFS_cyc(int v, int p)
{
    M[v] = 1;
    for (int &u : Adj[v])
        if (u != p && M[u] <= 1)
        {
            if (M[u])
            {
                cyc.pb(v);
                rev[v] = (int)cyc.size();
                return (u);
            }
            int w = DFS_cyc(u, v);
            if (w == -1)
                continue;
            if (w == -2)
                return (-2);

            cyc.pb(v);
            rev[v] = (int)cyc.size();
            if (w == v)
                return -2;
            return (w);
        }
    return (-1);
}
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]];
    SS.erase(SS.lower_bound(mxd[cyc[i]] - i));
}
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 ... */

    DFS_cyc(1, 0);

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

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

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

    /* 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 main()':
shymbulak.cpp:108:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < (int)cyc.size(); i++)
     ^~~
shymbulak.cpp:109:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         DFS(cyc[i], 0);m
                        ^
shymbulak.cpp:109:24: error: 'm' was not declared in this scope
shymbulak.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
shymbulak.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &u);
         ~~~~~^~~~~~~~~~~~~~~~