Submission #114955

#	Time	Username	Problem	Language	Result	Execution time	Memory
114955		mrboorger	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	74 ms	9880 KiB

shymbulak

#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define F first
#define S second
#define pb push_back
#define mp make_pair

using namespace std;

const ll inf = 1e18 + 18;
const int maxn = 200005;

int used[maxn];
bool cycle[maxn];
int depth[maxn];
pair <int, int> cc[maxn]; // {len, cnt}
vector <int> g[maxn];
int cyclesz = 0;

vector <int> path;
bool f = false;
void findcycle(int v, int pr)
{
    used[v] = 1;
    path.pb(v);
    for(int to:g[v])
    {
        if (used[to] == 0)
        {
            findcycle(to, v);
            if (f) return; //
        }
        if (used[to] == 1 && pr != to)
        {
            f = true;
            cycle[to] = true;
            cyclesz = 1;
            while(path.back() != to)
            {
                cycle[path.back()] = true;
                path.pop_back();
                cyclesz++;
            }
            return;
        }
    }
    path.pop_back();
    used[v] = 2;
    return;
}

int maxdepth;
int maxdepth2;
int cnt;
int cnt2;

void dfs(int v, int pr, int Depth)
{
    if (Depth > maxdepth && int(g[v].size() == 1))
    {
        maxdepth2 = maxdepth;
        maxdepth = Depth;
        cnt2 = cnt;
        cnt = 1;
    }
    else
    if (Depth == maxdepth && int(g[v].size() == 1))
    {
        maxdepth2 = maxdepth;
        cnt++;
    }

    depth[v] = Depth;

    for(int to:g[v])
    {
        if (to != pr && !cycle[to])
        {
            dfs(to, v, Depth + 1);
        }
    }
    return;
}

main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int len = 0;
    int ans = 0; //ll
    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        g[x].pb(y);
        g[y].pb(x);
    }
    findcycle(0, 0);
    for(int i = 0; i < n; i++)
    {
        if (cycle[i])
        {
            maxdepth = 0;
            maxdepth2 = 0;
            cnt = 1;
            cnt2 = 1;
            dfs(i, i, 0);
            cc[i] = {maxdepth, cnt};
            if (maxdepth + maxdepth2 > len)
            {
                len = maxdepth + maxdepth2;
                if (maxdepth2 < maxdepth)ans = cnt * cnt2;
                    else ans = (cnt * (cnt - 1)) / 2;
            }
            else
            if (maxdepth + maxdepth2 == len)
            {
                if (maxdepth2 < maxdepth) ans += cnt * cnt2;
                    else ans += (cnt * (cnt - 1)) / 2;
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        if (cycle[i])
        {
            for(int j:g[i])
            {
                if (cycle[j])
                {
                    //obhod
                    int v = j;
                    int pr = i;
                    int LEN = cc[i].F;
                    int CNT = cc[i].S;
                    int t = (cyclesz >> 1);
                    for(t; t > 0; t--)
                    {
                        LEN++;
                        int to;
                        for(auto ttt:g[v])
                        {
                            if (cycle[ttt] && ttt != pr)
                            {
                                to = ttt;
                                break;
                            }
                        }
                        if (LEN + cc[to].F > len)
                        {
                            len = LEN + cc[to].F;
                            ans = CNT * cc[to].S;
                        }
                        else
                        if (LEN + cc[to].F == len)
                        {
                            ans += CNT * cc[to].S;
                        }
                    }
                }
            }
        }
    }
    cout << (ans >> 1);
    return 0;
}

Compilation message (stderr)

shymbulak.cpp:87:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:151:26: warning: statement has no effect [-Wunused-value]
                     for(t; t > 0; t--)
                          ^
shymbulak.cpp:6:11: warning: 'to' may be used uninitialized in this function [-Wmaybe-uninitialized]
 #define S second
           ^~~~~~
shymbulak.cpp:154:29: note: 'to' was declared here
                         int to;
                             ^~

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