oj.uz

Submission #159430

# Submission time Handle Problem Language Result Execution time Memory
159430 2019-10-22T17:07:28 Z Minnakhmetov Duathlon (APIO18_duathlon) C++14
0 / 100
 117 ms 22484 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
  
using namespace std;

struct E {
    int to, i;
};

const int N = 1e5 + 5;
vector<E> g[N];
vector<int> g2[N], t[N];
int tin[N], mt[N], col[N], sz[N], sum[N];
int timer = 0, n, m;
bool used[N];

void dfs(int node, int anc) {
    used[node] = 1;
    tin[node] = ++timer;
    mt[node] = tin[node];
    for (E e : g[node]) {
        if (e.i != anc) {

            if (!used[e.to]) {
                dfs(e.to, e.i);
            }

            mt[node] = min(mt[node], mt[e.to]);

            if (mt[e.to] <= tin[node]) {
                g2[node].push_back(e.to);
                g2[e.to].push_back(node);
            }
        }
    }
}

void deep(int node, int c) {
    col[node] = c;
    used[node] = 1;

    sz[col[node]]++;

    for (int to : g2[node]) {
        if (!used[to]) {
            deep(to, c);
        }
    }

    for (E e : g[node]) {
        if (used[e.to] && col[e.to] != col[node]) {
            t[col[node]].push_back(col[e.to]);
            t[col[e.to]].push_back(col[node]);
        }
    }
}

ll ans = 0;

void dive(int node, int anc) {
    ans += sz[node] * (ll)(sz[node] - 1) * (sz[node] - 2);

    sum[node] = sz[node];

    used[node] = 1;

    for (int to : t[node]) {
        if (to != anc) {
            dive(to, node);
            sum[node] += sum[to];
        }
    }

    for (int to : t[node]) {
        int s = 0;
        if (to == anc)
            s = n - sum[node];
        else
            s = sum[to];

        ans += sz[node] * (ll)s * (n - s - sz[node]);

        ans += (sz[node] * (ll)(sz[node] - 1) - sz[node] + 1) * s * 2;
    }
}

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

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    dfs(0, -1);

    int cc = 0;

    fill(used, used + n, 0);

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            deep(i, cc++);
        }
    }

    fill(used, used + cc, 0);

    for (int i = 0; i < cc; i++) {
        if (!used[i]) {
            dive(i, -1);
        }
    }

    cout << ans;


    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 22420 KB Output is correct
2 Correct 108 ms 22484 KB Output is correct
3 Incorrect 106 ms 19708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 17656 KB Output is correct
2 Correct 105 ms 17728 KB Output is correct
3 Correct 106 ms 17640 KB Output is correct
4 Correct 98 ms 17784 KB Output is correct
5 Correct 100 ms 17656 KB Output is correct
6 Correct 102 ms 21240 KB Output is correct
7 Correct 99 ms 20216 KB Output is correct
8 Correct 113 ms 19420 KB Output is correct
9 Correct 112 ms 18976 KB Output is correct
10 Incorrect 102 ms 17828 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 17628 KB Output is correct
2 Correct 91 ms 17496 KB Output is correct
3 Incorrect 117 ms 18168 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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