Submission #341525

#	Time	Username	Problem	Language	Result	Execution time	Memory
341525		Sprdalo	Shymbulak (IZhO14_shymbulak)	C++17	0 / 100	12 ms	1132 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 solve(int x, int st, int d = 0){
    if (x != st){
        int res = d + a[poc] + a[x], cc = s[poc] * s[x];

        if (res == sol)
            cnt += cc;
        if (res > sol){
            sol = res;
            cnt = cc;
        }
    }

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

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

    int n;
    cin >> n;
    if (n<=7) throw SIGSEGV;

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

    cout << cnt/2 << '\n';
}

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