oj.uz

Submission #96232

# Submission time Handle Problem Language Result Execution time Memory
96232 2019-02-07T11:16:24 Z Kastanda Shymbulak (IZhO14_shymbulak) C++11
100 / 100
 160 ms 18516 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];

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

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: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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 6 ms 5880 KB Output is correct
3 Correct 8 ms 5880 KB Output is correct
4 Correct 6 ms 5748 KB Output is correct
5 Correct 7 ms 5924 KB Output is correct
6 Correct 7 ms 5880 KB Output is correct
7 Correct 7 ms 5880 KB Output is correct
8 Correct 6 ms 5836 KB Output is correct
9 Correct 6 ms 5880 KB Output is correct
10 Correct 8 ms 5880 KB Output is correct
11 Correct 6 ms 5840 KB Output is correct
12 Correct 6 ms 5884 KB Output is correct
13 Correct 6 ms 5880 KB Output is correct
14 Correct 6 ms 5852 KB Output is correct
15 Correct 6 ms 6008 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5880 KB Output is correct
2 Correct 7 ms 5900 KB Output is correct
3 Correct 6 ms 5880 KB Output is correct
4 Correct 6 ms 5880 KB Output is correct
5 Correct 12 ms 6136 KB Output is correct
6 Correct 7 ms 6136 KB Output is correct
7 Correct 10 ms 6136 KB Output is correct
8 Correct 8 ms 6136 KB Output is correct
9 Correct 7 ms 6136 KB Output is correct
10 Correct 8 ms 6136 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10276 KB Output is correct
2 Correct 67 ms 10744 KB Output is correct
3 Correct 56 ms 15092 KB Output is correct
4 Correct 46 ms 11000 KB Output is correct
5 Correct 46 ms 11000 KB Output is correct
6 Correct 160 ms 14308 KB Output is correct
7 Correct 107 ms 12792 KB Output is correct
8 Correct 91 ms 16028 KB Output is correct
9 Correct 102 ms 15864 KB Output is correct
10 Correct 86 ms 16760 KB Output is correct
11 Correct 93 ms 15500 KB Output is correct
12 Correct 101 ms 18516 KB Output is correct