oj.uz

Submission #393572

# Submission time Handle Problem Language Result Execution time Memory
393572 2021-04-24T03:51:45 Z KoD Duathlon (APIO18_duathlon) C++17
71 / 100
 335 ms 33792 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;
    if (N <= 10) {
        Vec<Vec<bool>> adj(N, Vec<bool>(N));
        for (int i = 0; i < M; ++i) {
            int a, b;
            std::cin >> a >> b;
            a -= 1;
            b -= 1;
            adj[a][b] = adj[b][a] = true;
        }
        Vec<Vec<Vec<bool>>> ans(N, Vec<Vec<bool>>(N, Vec<bool>(N)));
        Vec<Vec<Vec<bool>>> done(N, Vec<Vec<bool>>(N, Vec<bool>(1 << N)));
        const auto dfs = RecLambda([&](auto&& dfs, const int cur, const int fir, const int mid) -> void {
            if (done[cur][fir][mid]) return;
            done[cur][fir][mid] = true;
            if (cur == fir) {
                for (int i = 0; i < N; ++i) {
                    if (adj[cur][i]) {
                        dfs(i, cur, mid);
                    }
                }
            }
            else {
                for (int i = 0; i < N; ++i) {
                    if (i == cur or i == fir) continue;
                    if (mid >> i & 1) {
                        ans[fir][i][cur] = true;
                    }
                    else if (adj[cur][i]) {
                        dfs(i, fir, mid | (1 << cur));
                    }
                }
            }
        });
        for (int i = 0; i < N; ++i) {
            dfs(i, i, 0);
        }
        int cnt = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                for (int k = 0; k < N; ++k) {
                    if (ans[i][j][k]) {
                        cnt += 1;
                    }
                }
            }
        }
        std::cout << cnt << '\n';
        return 0;
    }
    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
5.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 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 292 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 296 KB Output is correct
28 Correct 1 ms 292 KB Output is correct
29 Correct 1 ms 296 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 292 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct

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 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 292 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 296 KB Output is correct
28 Correct 1 ms 292 KB Output is correct
29 Correct 1 ms 296 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 292 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Incorrect 1 ms 204 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 21080 KB Output is correct
2 Correct 121 ms 21036 KB Output is correct
3 Correct 195 ms 25748 KB Output is correct
4 Correct 165 ms 22568 KB Output is correct
5 Correct 142 ms 21308 KB Output is correct
6 Correct 200 ms 25076 KB Output is correct
7 Correct 192 ms 23484 KB Output is correct
8 Correct 197 ms 24016 KB Output is correct
9 Correct 182 ms 22076 KB Output is correct
10 Correct 177 ms 21428 KB Output is correct
11 Correct 162 ms 20412 KB Output is correct
12 Correct 144 ms 20140 KB Output is correct
13 Correct 148 ms 20848 KB Output is correct
14 Correct 130 ms 20584 KB Output is correct
15 Correct 110 ms 21268 KB Output is correct
16 Correct 145 ms 20796 KB Output is correct
17 Correct 21 ms 16084 KB Output is correct
18 Correct 22 ms 16068 KB Output is correct
19 Correct 20 ms 16112 KB Output is correct
20 Correct 24 ms 16044 KB Output is correct
21 Correct 20 ms 16116 KB Output is correct
22 Correct 20 ms 16120 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 556 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 2 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 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 2 ms 460 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 26132 KB Output is correct
2 Correct 279 ms 26080 KB Output is correct
3 Correct 295 ms 26100 KB Output is correct
4 Correct 288 ms 26180 KB Output is correct
5 Correct 296 ms 26164 KB Output is correct
6 Correct 290 ms 33792 KB Output is correct
7 Correct 284 ms 31416 KB Output is correct
8 Correct 279 ms 29980 KB Output is correct
9 Correct 335 ms 28604 KB Output is correct
10 Correct 276 ms 26160 KB Output is correct
11 Correct 272 ms 26200 KB Output is correct
12 Correct 284 ms 26112 KB Output is correct
13 Correct 267 ms 26196 KB Output is correct
14 Correct 222 ms 25720 KB Output is correct
15 Correct 230 ms 25256 KB Output is correct
16 Correct 153 ms 23216 KB Output is correct
17 Correct 183 ms 27428 KB Output is correct
18 Correct 181 ms 27284 KB Output is correct
19 Correct 212 ms 27552 KB Output is correct
20 Correct 195 ms 27308 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 464 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 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 332 KB Output is correct
11 Correct 2 ms 332 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 2 ms 464 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 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 4 ms 492 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 247 ms 26184 KB Output is correct
2 Correct 250 ms 25912 KB Output is correct
3 Correct 213 ms 22248 KB Output is correct
4 Correct 180 ms 19168 KB Output is correct
5 Correct 151 ms 16512 KB Output is correct
6 Correct 148 ms 15520 KB Output is correct
7 Correct 137 ms 15108 KB Output is correct
8 Correct 132 ms 14404 KB Output is correct
9 Correct 137 ms 14280 KB Output is correct
10 Correct 130 ms 14084 KB Output is correct
11 Correct 114 ms 13788 KB Output is correct
12 Correct 123 ms 13656 KB Output is correct
13 Correct 112 ms 13724 KB Output is correct
14 Correct 121 ms 15524 KB Output is correct
15 Correct 280 ms 27160 KB Output is correct
16 Correct 258 ms 25516 KB Output is correct
17 Correct 221 ms 24132 KB Output is correct
18 Correct 232 ms 22788 KB Output is correct
19 Correct 183 ms 19156 KB Output is correct
20 Correct 202 ms 19136 KB Output is correct
21 Correct 174 ms 19168 KB Output is correct
22 Correct 192 ms 18544 KB Output is correct
23 Correct 139 ms 17700 KB Output is correct
24 Correct 218 ms 22668 KB Output is correct
25 Correct 226 ms 22584 KB Output is correct
26 Correct 185 ms 20336 KB Output is correct
27 Correct 207 ms 20264 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 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 292 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 296 KB Output is correct
28 Correct 1 ms 292 KB Output is correct
29 Correct 1 ms 296 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 292 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Incorrect 1 ms 204 KB Output isn't correct
39 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 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 292 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 296 KB Output is correct
28 Correct 1 ms 292 KB Output is correct
29 Correct 1 ms 296 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 292 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Incorrect 1 ms 204 KB Output isn't correct
39 Halted 0 ms 0 KB -