oj.uz

Submission #171470

# Submission time Handle Problem Language Result Execution time Memory
171470 2019-12-28T17:29:34 Z VEGAnn Shymbulak (IZhO14_shymbulak) C++14
30 / 100
 1500 ms 860 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pll pair<ll, ll>
#define pii pair<int, int>
using namespace std;
typedef long long ll;
const ll OO = 1e18;
const int oo = 2e9;
const int N = 5100;
const int M = 1010;
vector<int> g[N], vc, cyc;
set<pii> st;
bool in_cyc[N];
int n, ans = 0, dst[N], mx = 0, mrk[N], up[N], pos[N];

void CYCLE(int lst){
    cyc.clear();
    int it = sz(vc) - 1;
    while (1){
        cyc.PB(vc[it]);
        in_cyc[vc[it]] = 1;
        if (vc[it] == lst)
            break;
        it--;
    }
}

void dfs(int v, int p){
    if (sz(cyc) > 0) return;
    vc.PB(v);
    mrk[v] = 1;
    for (int u : g[v]){
        if (u == p) continue;
        if (mrk[u] == 0)
            dfs(u, v); else
        if (mrk[u] == 1)
            CYCLE(u);
    }
    mrk[v] = 2;
    vc.pop_back();
}

void DFS(int v, int p){
    for (int u : g[v]){
        if (u == p || in_cyc[u]) continue;
        up[u] = up[v];
        DFS(u, v);
    }
}

bool ok(int x, int y){
    if (sz(cyc) & 1) return 0;
    if (pos[up[x]] < pos[up[y]])
        swap(x, y);
    return (pos[up[x]] - pos[up[y]]) == (sz(cyc) >> 1);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    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);
    }
    dfs(0, -1);
    for (int it = 0; it < sz(cyc); it++) {
        int cr = cyc[it];
        pos[cr] = it;
        up[cr] = cr;
        DFS(cr, -1);
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++) {
            dst[j] = oo;
        }
        dst[i] = 0;
        st.insert(MP(0, i));
        while (sz(st)){
            int v = (*st.begin()).sd;
            st.erase(st.begin());
            for (int u : g[v])
                if (dst[u] > dst[v] + 1){
                    st.erase(MP(dst[u], u));
                    dst[u] = dst[v] + 1;
                    st.insert(MP(dst[u], u));
                }
        }
        for (int v = i + 1; v < n; v++) {
            if (dst[v] > mx) {
                mx = dst[v];
                ans = 0;
            }
            if (dst[v] == mx)
                ans += (ok(i, v) ? 2 : 1);
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 51 ms 504 KB Output is correct
15 Correct 37 ms 560 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 504 KB Output is correct
2 Correct 116 ms 604 KB Output is correct
3 Correct 87 ms 592 KB Output is correct
4 Correct 175 ms 632 KB Output is correct
5 Execution timed out 1579 ms 860 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

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