oj.uz

Submission #218559

# Submission time Handle Problem Language Result Execution time Memory
218559 2020-04-02T09:33:58 Z VEGAnn Duathlon (APIO18_duathlon) C++14
23 / 100
 707 ms 1048580 KB 
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 200100;
set<int> st;
vector<int> g[N], adj[2 * N];
int n, m, tin[N], fup[N], pr[N], siz_comp[2 * N], siz[2 * N], tt = 0, U[M], V[M];
bool mrk[2 * N];
ll ans = 0ll;

int get(int x){ return (pr[x] == x ? x : pr[x] = get(pr[x])); }

void dfs0(int v, int p_edg){
    mrk[v] = 1;
    tin[v] = fup[v] = ++tt;

    for (int nm : g[v]){
        if (nm == p_edg) continue;

        int u = (U[nm] == v ? V[nm] : U[nm]);

        if (!mrk[u]){
            dfs0(u, nm);

            if (fup[u] < tin[v]){
                if (p_edg >= 0) pr[get(p_edg)] = get(nm);
            }

            fup[v] = min(fup[v], fup[u]);
        } else {
            fup[v] = min(fup[v], tin[u]);

            if (tin[u] < tin[v])
                pr[get(p_edg)] = get(nm);
        }
    }
}

void dfs(int v, int p){
    mrk[v] = 1;
    siz[v] = bool(v < n);

    for (int u : adj[v])
        if (u != p) {
            dfs(u, v);
            siz[v] += siz[u];
        }
}

void finally(int v, int r, int p){
    if (v < n){
        for (int u : adj[v]){
            assert(u >= n);

            if (u == p){
                ans -= (ll(siz_comp[u - n]) - 1ll) * (ll(siz[r]) - ll(siz[v]) - 1ll) *  (ll(siz[r]) - ll(siz[v]));
            } else {
                ans -= (ll(siz_comp[u - n]) - 1ll) * ll(siz[u]) * (ll(siz[u]) - 1ll);
            }
        }
    }

    for (int u : adj[v]){
        if (u == p) continue;
        finally(u, r, v);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        pr[i] = i;

        int x, y; cin >> x >> y;
        x--; y--;

        U[i] = x;
        V[i] = y;
        g[x].PB(i);
        g[y].PB(i);
    }

    for (int i = 0; i < n; i++)
        if (!mrk[i]) dfs0(i, -1);

    for (int v = 0; v < n; v++){
        st.clear();

        for (int nm : g[v])
            st.insert(get(nm));

        for (auto cp : st){
            siz_comp[cp]++;
            adj[cp + n].PB(v);
            adj[v].PB(cp + n);
        }
    }

    fill(mrk, mrk + n, 0);

    for (int v = 0; v < n; v++){
        if (mrk[v]) continue;

        dfs(v, -1);
        ans += ll(siz[v]) * (ll(siz[v]) - 1ll) * (ll(siz[v]) - 2ll);
        finally(v, v, -1);
    }

    cout << ans;

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 27120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 10 ms 7552 KB Output is correct
3 Correct 9 ms 7552 KB Output is correct
4 Correct 9 ms 7680 KB Output is correct
5 Correct 9 ms 7680 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 9 ms 7680 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct
9 Correct 9 ms 7552 KB Output is correct
10 Correct 9 ms 7552 KB Output is correct
11 Correct 10 ms 7552 KB Output is correct
12 Correct 9 ms 7552 KB Output is correct
13 Correct 9 ms 7552 KB Output is correct
14 Correct 9 ms 7552 KB Output is correct
15 Correct 10 ms 7552 KB Output is correct
16 Correct 9 ms 7552 KB Output is correct
17 Correct 9 ms 7680 KB Output is correct
18 Correct 9 ms 7552 KB Output is correct
19 Correct 9 ms 7680 KB Output is correct
20 Correct 10 ms 7680 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 21708 KB Output is correct
2 Correct 186 ms 21624 KB Output is correct
3 Correct 193 ms 21632 KB Output is correct
4 Correct 187 ms 21624 KB Output is correct
5 Correct 179 ms 21628 KB Output is correct
6 Correct 217 ms 28152 KB Output is correct
7 Correct 226 ms 25976 KB Output is correct
8 Correct 205 ms 24824 KB Output is correct
9 Correct 205 ms 23692 KB Output is correct
10 Correct 186 ms 21752 KB Output is correct
11 Correct 184 ms 21752 KB Output is correct
12 Correct 174 ms 21624 KB Output is correct
13 Correct 173 ms 21624 KB Output is correct
14 Correct 157 ms 20856 KB Output is correct
15 Correct 129 ms 19832 KB Output is correct
16 Correct 78 ms 16632 KB Output is correct
17 Correct 138 ms 25728 KB Output is correct
18 Correct 161 ms 23664 KB Output is correct
19 Correct 135 ms 22764 KB Output is correct
20 Correct 134 ms 22776 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Incorrect 10 ms 7552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 21752 KB Output is correct
2 Correct 180 ms 21496 KB Output is correct
3 Runtime error 707 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -