oj.uz

Submission #393571

# Submission time Handle Problem Language Result Execution time Memory
393571 2021-04-24T03:50:40 Z KoD Duathlon (APIO18_duathlon) C++17
66 / 100
 276 ms 33984 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(V);
    Vec<Vec<int>> edge(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);
            edge[A[i]].push_back(b);
            edge[B[i]].push_back(a);
            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);
        const ll sum = whole - size[u];
        ans += sum * sum * size[u];
        for (const auto c: group[u]) {
            ll sub = 0;
            for (const auto v: edge[c]) {
                const ll tmp = (v == p ? whole - subtree[u] : subtree[v]);
                ans -= tmp * tmp;
                sub += tmp;
            }
            ans -= sub * sub * size[u];
            ans += sub * sub;
        }
        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 204 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 208 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 204 KB Output isn't correct
9 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 204 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 208 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 204 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 21052 KB Output is correct
2 Correct 115 ms 21060 KB Output is correct
3 Correct 169 ms 25764 KB Output is correct
4 Correct 130 ms 22560 KB Output is correct
5 Correct 142 ms 21444 KB Output is correct
6 Correct 179 ms 25280 KB Output is correct
7 Correct 188 ms 23588 KB Output is correct
8 Correct 197 ms 23900 KB Output is correct
9 Correct 165 ms 22060 KB Output is correct
10 Correct 168 ms 21560 KB Output is correct
11 Correct 136 ms 20284 KB Output is correct
12 Correct 159 ms 20140 KB Output is correct
13 Correct 143 ms 20876 KB Output is correct
14 Correct 132 ms 20540 KB Output is correct
15 Correct 112 ms 21256 KB Output is correct
16 Correct 104 ms 20772 KB Output is correct
17 Correct 19 ms 16068 KB Output is correct
18 Correct 19 ms 16072 KB Output is correct
19 Correct 20 ms 16072 KB Output is correct
20 Correct 19 ms 16128 KB Output is correct
21 Correct 19 ms 16080 KB Output is correct
22 Correct 19 ms 16072 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 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 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 464 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 26196 KB Output is correct
2 Correct 232 ms 26208 KB Output is correct
3 Correct 236 ms 26300 KB Output is correct
4 Correct 246 ms 26124 KB Output is correct
5 Correct 234 ms 26124 KB Output is correct
6 Correct 264 ms 33984 KB Output is correct
7 Correct 250 ms 31336 KB Output is correct
8 Correct 241 ms 29996 KB Output is correct
9 Correct 244 ms 28596 KB Output is correct
10 Correct 276 ms 26272 KB Output is correct
11 Correct 243 ms 26300 KB Output is correct
12 Correct 275 ms 26188 KB Output is correct
13 Correct 236 ms 26168 KB Output is correct
14 Correct 254 ms 25884 KB Output is correct
15 Correct 192 ms 25276 KB Output is correct
16 Correct 120 ms 23036 KB Output is correct
17 Correct 164 ms 27332 KB Output is correct
18 Correct 176 ms 27332 KB Output is correct
19 Correct 169 ms 27484 KB Output is correct
20 Correct 177 ms 27440 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 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 344 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 2 ms 564 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 464 KB Output is correct
19 Correct 2 ms 464 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 432 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 432 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 1 ms 460 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 26144 KB Output is correct
2 Correct 227 ms 25916 KB Output is correct
3 Correct 200 ms 22440 KB Output is correct
4 Correct 176 ms 20632 KB Output is correct
5 Correct 164 ms 17964 KB Output is correct
6 Correct 162 ms 17020 KB Output is correct
7 Correct 128 ms 16332 KB Output is correct
8 Correct 122 ms 15728 KB Output is correct
9 Correct 122 ms 15556 KB Output is correct
10 Correct 120 ms 15360 KB Output is correct
11 Correct 122 ms 15104 KB Output is correct
12 Correct 121 ms 15036 KB Output is correct
13 Correct 121 ms 14992 KB Output is correct
14 Correct 149 ms 16872 KB Output is correct
15 Correct 232 ms 28704 KB Output is correct
16 Correct 212 ms 26956 KB Output is correct
17 Correct 210 ms 25744 KB Output is correct
18 Correct 206 ms 24336 KB Output is correct
19 Correct 177 ms 20664 KB Output is correct
20 Correct 179 ms 20660 KB Output is correct
21 Correct 177 ms 20668 KB Output is correct
22 Correct 166 ms 20128 KB Output is correct
23 Correct 150 ms 19008 KB Output is correct
24 Correct 185 ms 24020 KB Output is correct
25 Correct 191 ms 24156 KB Output is correct
26 Correct 168 ms 21820 KB Output is correct
27 Correct 167 ms 21820 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 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 208 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 204 KB Output isn't correct
9 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 204 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 208 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 204 KB Output isn't correct
9 Halted 0 ms 0 KB -