oj.uz

Submission #341522

# Submission time Handle Problem Language Result Execution time Memory
341522 2020-12-29T22:47:24 Z Sprdalo Shymbulak (IZhO14_shymbulak) C++17
0 / 100
 12 ms 1004 KB 
#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;

    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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 632 KB Output is correct
2 Incorrect 1 ms 620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 748 KB Output is correct
2 Incorrect 1 ms 620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -