oj.uz

Submission #217590

# Submission time Handle Problem Language Result Execution time Memory
217590 2020-03-30T10:20:25 Z VEGAnn Duathlon (APIO18_duathlon) C++14
23 / 100
 140 ms 19156 KB 
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 200100;
const int oo = 2e9;
vector<int> g[N], gr[N];
int n, m, tin[N], fup[N], tt = 0, U[M], V[M], pr[N], siz[N];
int nw_siz[N];
bool mrk[N], bridge[M];
ll ans = 0, SZ;

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

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

        if (u == p) continue;

        if (mrk[u])
            fup[v] = min(fup[v], tin[u]);
        else {
            dfs(u, v);
            fup[v] = min(fup[v], fup[u]);

            if (fup[u] > tin[v])
                bridge[nm] = 1;
        }
    }
}

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

void dfs1(int v, int p){
    nw_siz[v] = siz[v];
    mrk[v] = 1;

    for (int u : gr[v]){
        if (u == p) continue;

        dfs1(u, v);
        nw_siz[v] += nw_siz[u];
    }
}

void dfs2(int v, int p){
    ans += ll(siz[v]) * (ll(siz[v]) - 1ll) * (ll(siz[v]) - 2ll) / 6ll; // first

    ans += (SZ - ll(siz[v])) * (ll(siz[v])) * (ll(siz[v]) - 1ll);

    ll sum = 0ll;

    for (int u : gr[v]){
        if (u == p) continue;

        dfs2(u, v);

        ans += sum * ll(siz[v]) * ll(nw_siz[u]);

        sum += nw_siz[u];
    }

    ans += sum * ll(siz[v]) * (SZ - ll(nw_siz[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++){
        cin >> U[i] >> V[i];
        U[i]--; V[i]--;

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

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

        pr[i] = i;
        siz[i] = 1;
    }


    for (int i = 0; i < m; i++) {
        if (bridge[i]) continue;

        int x = get(U[i]), y = get(V[i]);

        if (x == y) continue;

        pr[x] = y;
        siz[y] += siz[x];
    }

    for (int i = 0; i < m; i++)
        if (bridge[i]){
            int x = get(U[i]), y = get(V[i]);

            gr[x].PB(y);
            gr[y].PB(x);
        }

    fill(mrk, mrk + n, 0);

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

        dfs1(i, -1);
        SZ = nw_siz[i];
        dfs2(i, -1);
    }

    cout << ans * 2;

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 19064 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 8 ms 5120 KB Output is correct
2 Correct 10 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5248 KB Output is correct
7 Correct 8 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 9 ms 5248 KB Output is correct
11 Correct 8 ms 5120 KB Output is correct
12 Correct 7 ms 5248 KB Output is correct
13 Correct 8 ms 5168 KB Output is correct
14 Correct 8 ms 5120 KB Output is correct
15 Correct 7 ms 5120 KB Output is correct
16 Correct 7 ms 5120 KB Output is correct
17 Correct 8 ms 5248 KB Output is correct
18 Correct 8 ms 5248 KB Output is correct
19 Correct 8 ms 5248 KB Output is correct
20 Correct 8 ms 5248 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 15224 KB Output is correct
2 Correct 98 ms 15104 KB Output is correct
3 Correct 97 ms 15096 KB Output is correct
4 Correct 103 ms 15096 KB Output is correct
5 Correct 101 ms 15096 KB Output is correct
6 Correct 140 ms 19156 KB Output is correct
7 Correct 120 ms 17784 KB Output is correct
8 Correct 119 ms 17020 KB Output is correct
9 Correct 113 ms 16252 KB Output is correct
10 Correct 95 ms 15096 KB Output is correct
11 Correct 100 ms 15100 KB Output is correct
12 Correct 103 ms 15096 KB Output is correct
13 Correct 108 ms 15096 KB Output is correct
14 Correct 100 ms 14840 KB Output is correct
15 Correct 82 ms 14584 KB Output is correct
16 Correct 54 ms 12920 KB Output is correct
17 Correct 61 ms 15728 KB Output is correct
18 Correct 62 ms 15732 KB Output is correct
19 Correct 61 ms 15980 KB Output is correct
20 Correct 62 ms 15736 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 14584 KB Output is correct
2 Correct 99 ms 14584 KB Output is correct
3 Incorrect 101 ms 14968 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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