Submission #115011

#	Time	Username	Problem	Language	Result	Execution time	Memory
115011		mrboorger	Shymbulak (IZhO14_shymbulak)	C++14	50 / 100	1530 ms	12916 KiB

shymbulak

#include <bits/stdc++.h>

#pragma optimize ("-Ofast")

#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];
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 len = 0;
ll ans = 0; //ll

pair <int, int> dfs(int v, int pr)
{
    vector <pair <int, ll>> vc;
    vc.pb({0, 1});
    for(int to:g[v])
    {
        if (to != pr && !cycle[to])
        {
            vc.pb(dfs(to, v));
            vc.back().F++;
        }
    }
    sort(vc.rbegin(), vc.rend());
    int n = int(vc.size());
    int i = 0;
    if (n == 1)
    {
        return vc[0];
    }
    if (vc[0].F == vc[1].F && vc[0].F * 2 >= len)
    {
        ll izm = 0;
        ll sum = 0;
        while(i < n && vc[i].F == vc[0].F)
        {
            sum += vc[i].S;
//            cerr << vc[i].S;
            i++;
        }
        i = 0;
       while(i < n && vc[i].F == vc[0].F)
       {
            izm += vc[i].S * (sum - vc[i].S);
            i++;
       }
       if (vc[0].F * 2 > len)
       {
           len = vc[0].F * 2;
           ans = izm;
       }
       else
       {
           ans += izm;
       }
    }
    else
    if (vc[0].F != vc[1].F && vc[0].F + vc[1].F >= len)
    {
        ll izm = 0;
        i = 1;
       while(i < n && vc[i].F == vc[1].F)
       {
            izm += vc[0].S * vc[i].S;
            i++;
       }
       if (vc[0].F + vc[1].F > len)
       {
           ans = izm * 2;
       }
       else
       {
           ans += izm * 2;
       }
       len = vc[0].F + vc[1].F;
    }
    i = 0;
    ll ret = 0;
    while(i < n && vc[i].F == vc[0].F)
    {
        ret += vc[i].S;
        i++;
    }
    return {vc[0].F, ret};
}

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;
    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])
        {
            pair <int, int> pp = dfs(i, i);
            cc[i] = pp;
        }
    }
    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 / 2;
                    for(t; t > 0; t--)
                    {
                        LEN++;
                        if (LEN + cc[v].F > len)
                        {
                            len = LEN + cc[v].F;
                            ans = CNT * cc[v].S;
                        }
                        else
                        if (LEN + cc[v].F == len)
                        {
                            ans += CNT * cc[v].S;
                        }
                        for(auto ttt:g[v])
                        {
                            if (cycle[ttt] && ttt != pr)
                            {
                                pr = v;
                                v = ttt;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
//    cerr << len << endl;
    cout << (ans >> 1);
    return 0;
}

Compilation message (stderr)

shymbulak.cpp:3:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize ("-Ofast")
 
shymbulak.cpp:134:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:180:26: warning: statement has no effect [-Wunused-value]
                     for(t; t > 0; t--)
                          ^

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