oj.uz

Submission #218575

# Submission time Handle Problem Language Result Execution time Memory
218575 2020-04-02T09:57:19 Z VEGAnn Duathlon (APIO18_duathlon) C++14
31 / 100
 694 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){
                ll cur = ll(siz_comp[u - n]) - 1ll;
//                if (cur == 1ll) cur = 0ll;
                ans -= (ll(siz_comp[u - n]) - 1ll) * (ll(siz[r]) - ll(siz[v]) - 1ll - cur) *  (ll(siz[r]) - ll(siz[v]) - cur);
            } else {
                ll cur = ll(siz_comp[u - n]) - 1ll;
//                if (cur == 1ll) cur = 0ll;
                ans -= (ll(siz_comp[u - n]) - 1ll) * (ll(siz[u]) - cur) * (ll(siz[u]) - 1ll - cur);
            }
        }
    } else {
        for (int u : adj[v]){
            assert(u < n);

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

    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 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Incorrect 9 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Incorrect 9 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 27248 KB Output is correct
2 Correct 102 ms 27120 KB Output is correct
3 Correct 163 ms 25204 KB Output is correct
4 Correct 132 ms 26352 KB Output is correct
5 Correct 152 ms 22896 KB Output is correct
6 Correct 174 ms 24308 KB Output is correct
7 Correct 169 ms 22648 KB Output is correct
8 Correct 200 ms 23060 KB Output is correct
9 Correct 169 ms 21496 KB Output is correct
10 Correct 158 ms 21832 KB Output is correct
11 Correct 121 ms 19320 KB Output is correct
12 Correct 130 ms 19192 KB Output is correct
13 Correct 118 ms 18808 KB Output is correct
14 Correct 107 ms 18424 KB Output is correct
15 Correct 83 ms 16888 KB Output is correct
16 Correct 106 ms 16760 KB Output is correct
17 Correct 12 ms 8704 KB Output is correct
18 Correct 12 ms 8704 KB Output is correct
19 Correct 11 ms 8704 KB Output is correct
20 Correct 11 ms 8704 KB Output is correct
21 Correct 11 ms 8704 KB Output is correct
22 Correct 11 ms 8704 KB Output is correct

Subtask #4
10.0 / 10.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 Correct 10 ms 7552 KB Output is correct
4 Correct 10 ms 7632 KB Output is correct
5 Correct 10 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 12 ms 7552 KB Output is correct
9 Correct 9 ms 7680 KB Output is correct
10 Correct 9 ms 7552 KB Output is correct
11 Correct 9 ms 7552 KB Output is correct
12 Correct 10 ms 7552 KB Output is correct
13 Correct 9 ms 7552 KB Output is correct
14 Correct 10 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 10 ms 7680 KB Output is correct
19 Correct 11 ms 7552 KB Output is correct
20 Correct 10 ms 7552 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 21728 KB Output is correct
2 Correct 189 ms 21624 KB Output is correct
3 Correct 183 ms 21624 KB Output is correct
4 Correct 225 ms 21628 KB Output is correct
5 Correct 194 ms 21624 KB Output is correct
6 Correct 219 ms 28152 KB Output is correct
7 Correct 212 ms 25848 KB Output is correct
8 Correct 212 ms 24824 KB Output is correct
9 Correct 202 ms 23672 KB Output is correct
10 Correct 183 ms 21624 KB Output is correct
11 Correct 191 ms 21624 KB Output is correct
12 Correct 183 ms 21624 KB Output is correct
13 Correct 184 ms 21624 KB Output is correct
14 Correct 170 ms 20856 KB Output is correct
15 Correct 134 ms 19960 KB Output is correct
16 Correct 81 ms 16532 KB Output is correct
17 Correct 139 ms 25712 KB Output is correct
18 Correct 148 ms 23664 KB Output is correct
19 Correct 136 ms 22764 KB Output is correct
20 Correct 140 ms 22776 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Incorrect 9 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 194 ms 21624 KB Output is correct
2 Correct 194 ms 21496 KB Output is correct
3 Runtime error 694 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 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Incorrect 9 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Incorrect 9 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -