Submission #343041

#	Time	Username	Problem	Language	Result	Execution time	Memory
343041		Sprdalo	Shymbulak (IZhO14_shymbulak)	C++17	0 / 100	12 ms	1644 KiB

shymbulak

#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

const int maxn = 5010;
vi e[maxn], cyc(maxn), vis(maxn);
stack<int> st;
bool ciklus = 0;
int len;

void stek(int x){
    ciklus = 1;
    while(!st.empty()){
        cyc[st.top()] = 1;
        ++len;
        if (st.top() == x) break;
        st.pop();
    }
}

void cycle(int x, int start){
    vis[x] = 1;
    st.push(x);
    for (int y : e[x]){
        if (start == y) continue;
        if (vis[y]){
            stek(y);
            break;
        }
        cycle(y, x);
        if (ciklus) break;
    }
    if (ciklus) return;
    st.pop();
}

vi a(maxn, -1), s(maxn);
int poc;
void calc(int x, int st, int d = 0){
    if (d > a[poc]){
        a[poc] = d;
        s[poc] = 1;
    } else if (d == a[poc]){
        s[poc]++;
    }

    for (int i : e[x])
        if (i != st && !cyc[i])
            calc(i, x, d+1);
}

int sol, cnt;

void update(int res, int cc){
    if (res == sol)
            cnt += cc;
    if (res > sol){
        sol = res;
        cnt = cc;
    }
}

void solve(int x, int st, int d = 0){
    if (x != st){
        int res = d + a[poc] + a[x], cc = s[poc] * s[x];
        update(res, cc);
    }

    for (int i : e[x])
        if (i != st && cyc[i] && 2 * (d+1) <= len)
            solve(i, x, d+1);
}

int d, cc;
void unutra(int x, int st, int dist = 1){
    if (dist == d) ++cc;
    if (dist > d){
        d = dist;
        cc = 1;
    }

    for (int y : e[x]){
        if (y != st)
            unutra(y, x, dist+1);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i){
        int u, v;
        cin >> u >> v;

        e[u].push_back(v);
        e[v].push_back(u);
    }

    cycle(1, 1);

    for (int i = 1; i <= n; ++i){
        if (!cyc[i]) continue;
        poc = i;
        calc(i, i);
    }

    for (int i = 1; i <= n; ++i){
        if (cyc[i]){
            poc = i;
            solve(i,i);
        }
    }

    int test = 0;
    for (int i = 1; i <= n; ++i){
        if (!cyc[i]) continue;

        vp t;
        for (int j : e[i]){
            if (cyc[j]) continue;
            d = 0; cc = 0;
            unutra(j, i);
            t.push_back({d, cc});
        }

        sort(t.rbegin(), t.rend());

        if (t.empty()) continue;
        int sz = t.size();

        if (sz == 1){
            update(t[0].first, t[0].second*2);
            continue;
        }

        int br = 0, u = t[1].second;
        for (int j = 2; j < sz; ++j){
            if (t[j].first != t[1].first) break;
            ++br;
            u += t[j].second;
        }

        if (t[0].first == t[1].first){
            int g = 0;
            u += t[0].second;

            for (int j = 0; j < sz; ++j){
                if (t[j].first != t[0].first) break;
                g += (u - t[j].second) * t[j].second;
            }

            int ta = sol, tb= cnt;
            update(t[0].first*2, g);
            if (sol != ta || cnt != tb)
                test = 1;
            continue;
        }

        int ta = sol, tb = cnt;
        update(t[0].first + t[1].first, u * t[0].second*2);
        if (ta != sol || tb != cnt)
            test=2;
    }

    if (test==2) throw SIGSEGV;
    cout << cnt/2 << '\n';
}

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