oj.uz

Submission #393565

# Submission time Handle Problem Language Result Execution time Memory
393565 2021-04-24T03:22:41 Z KoD Duathlon (APIO18_duathlon) C++17
31 / 100
 186 ms 27452 KB 
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

using ll = long long;

template <class F>
struct RecLambda: private F {
    explicit RecLambda(F&& f): F(std::forward<F>(f)) { }
    template <class... Args>
    decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};      

struct DSU {
    Vec<int> par;
    DSU(const int n): par(n, -1) { }
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        par[x] += par[y];
        par[y] = x;
    }
};

int main() {
    int N, M;
    std::cin >> N >> M;
    Vec<Vec<std::pair<int, int>>> graph(N);
    Vec<int> A(M), B(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i];
        A[i] -= 1;
        B[i] -= 1;
        graph[A[i]].emplace_back(B[i], i);
        graph[B[i]].emplace_back(A[i], i);
    }
    Vec<bool> bridge(M);
    Vec<int> ord(N), low(N);
    {
        Vec<int> depth(N, -1);
        int time = 0;
        const auto dfs = RecLambda([&](auto&& dfs, const int u, const int p, const int d) -> void {
            depth[u] = d;
            ord[u] = time++;
            low[u] = ord[u];
            for (const auto [v, e]: graph[u]) {
                if (depth[v] == -1) {
                    dfs(v, u, d + 1);
                    if (low[v] > ord[u]) {
                        bridge[e] = true;
                    }
                    low[u] = std::min(low[u], low[v]);
                }
                else if (v != p and depth[v] < depth[u]) {
                    low[u] = std::min(low[u], ord[v]);
                }
            }
        });
        for (int i = 0; i < N; ++i) {
            if (depth[i] == -1) {
                dfs(i, i, 0);
            }
        }
    }
    DSU dsu(N);
    for (int i = 0; i < M; ++i) {
        if (!bridge[i]) {
            dsu.merge(A[i], B[i]);
        }
    }
    Vec<Vec<int>> group(N);
    for (int i = 0; i < N; ++i) {
        group[dsu.find(i)].push_back(i);
    }
    group.erase(std::remove_if(group.begin(), group.end(), [&](const auto &v) { return v.empty(); }), group.end());
    const auto V = (int) group.size();
    Vec<int> belong(N);
    Vec<int> size(V);
    for (int i = 0; i < V; ++i) {
        size[i] = (int) group[i].size();
        for (const auto u: group[i]) {
            belong[u] = i;
        }
    }
    Vec<Vec<int>> tree(N);
    for (int i = 0; i < M; ++i) {
        if (bridge[i]) {
            const auto a = belong[A[i]];
            const auto b = belong[B[i]];
            assert(a != b);
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
    }
    ll ans = 0;
    for (int i = 0; i < V; ++i) {
        const ll x = size[i];
        ans += x * (x - 1) * (x - 2);
    }
    Vec<bool> visited(V);
    Vec<int> subtree(V);
    const auto setup = RecLambda([&](auto&& dfs, const int u) -> void {
        visited[u] = true;
        subtree[u] = size[u];
        for (const auto v: tree[u]) {
            if (!visited[v]) {
                dfs(v);
                subtree[u] += subtree[v];
            }
        }
    });
    Vec<int> root;
    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {
            root.push_back(i);
            setup(i);
        }
    }
    const auto apply = RecLambda([&](auto&& dfs, const int u, const int p, const int whole) -> void {
        const auto len = (int) tree[u].size();
        Vec<int> around(len);
        for (int i = 0; i < len; ++i) {
            const auto v = tree[u][i];
            if (v == p) {
                around[i] = whole - subtree[u];
            }
            else {
                around[i] = subtree[v];
            }
        }
        const ll sum = whole - size[u];
        ans += sum * sum * size[u];
        for (const ll x: around) {
            ans -= x * x * size[u];
        }
        ans += (ll) (size[u] - 1) * (size[u] - 1) * sum * 2;
        for (const auto v: tree[u]) {
            if (v != p) {
                dfs(v, u, whole);
            }
        }
    });
    for (const auto r: root) {
        apply(r, r, subtree[r]);
    }
    std::cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Incorrect 1 ms 204 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 113 ms 21076 KB Output is correct
2 Correct 124 ms 21112 KB Output is correct
3 Correct 145 ms 22300 KB Output is correct
4 Correct 130 ms 22428 KB Output is correct
5 Correct 143 ms 20412 KB Output is correct
6 Correct 138 ms 22736 KB Output is correct
7 Correct 143 ms 21112 KB Output is correct
8 Correct 150 ms 21612 KB Output is correct
9 Correct 146 ms 19808 KB Output is correct
10 Correct 140 ms 19876 KB Output is correct
11 Correct 112 ms 18092 KB Output is correct
12 Correct 116 ms 18084 KB Output is correct
13 Correct 106 ms 18360 KB Output is correct
14 Correct 104 ms 18132 KB Output is correct
15 Correct 86 ms 18108 KB Output is correct
16 Correct 84 ms 17848 KB Output is correct
17 Correct 17 ms 13724 KB Output is correct
18 Correct 17 ms 13780 KB Output is correct
19 Correct 17 ms 13684 KB Output is correct
20 Correct 17 ms 13704 KB Output is correct
21 Correct 17 ms 13728 KB Output is correct
22 Correct 17 ms 13768 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 20572 KB Output is correct
2 Correct 148 ms 20576 KB Output is correct
3 Correct 172 ms 20664 KB Output is correct
4 Correct 156 ms 20732 KB Output is correct
5 Correct 148 ms 20524 KB Output is correct
6 Correct 174 ms 27452 KB Output is correct
7 Correct 186 ms 25388 KB Output is correct
8 Correct 166 ms 24064 KB Output is correct
9 Correct 160 ms 22864 KB Output is correct
10 Correct 172 ms 20540 KB Output is correct
11 Correct 156 ms 21904 KB Output is correct
12 Correct 168 ms 21820 KB Output is correct
13 Correct 144 ms 21744 KB Output is correct
14 Correct 156 ms 21332 KB Output is correct
15 Correct 130 ms 20964 KB Output is correct
16 Correct 88 ms 18992 KB Output is correct
17 Correct 121 ms 22704 KB Output is correct
18 Correct 116 ms 22604 KB Output is correct
19 Correct 118 ms 22756 KB Output is correct
20 Correct 117 ms 22608 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 20508 KB Output is correct
2 Correct 168 ms 20364 KB Output is correct
3 Incorrect 170 ms 18372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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