oj.uz

Submission #393573

# Submission time Handle Problem Language Result Execution time Memory
393573 2021-04-24T03:51:57 Z KoD Duathlon (APIO18_duathlon) C++17
71 / 100
 286 ms 33832 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 1 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 324 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 208 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 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 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 0 ms 204 KB Output is correct
27 Correct 1 ms 208 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 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 1 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 324 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 208 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 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 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 0 ms 204 KB Output is correct
27 Correct 1 ms 208 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 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 126 ms 21100 KB Output is correct
2 Correct 132 ms 21096 KB Output is correct
3 Correct 195 ms 25708 KB Output is correct
4 Correct 156 ms 22596 KB Output is correct
5 Correct 154 ms 21444 KB Output is correct
6 Correct 215 ms 25112 KB Output is correct
7 Correct 204 ms 23424 KB Output is correct
8 Correct 217 ms 24012 KB Output is correct
9 Correct 202 ms 22020 KB Output is correct
10 Correct 196 ms 21408 KB Output is correct
11 Correct 165 ms 20284 KB Output is correct
12 Correct 160 ms 20148 KB Output is correct
13 Correct 158 ms 20996 KB Output is correct
14 Correct 153 ms 20540 KB Output is correct
15 Correct 133 ms 21320 KB Output is correct
16 Correct 119 ms 20792 KB Output is correct
17 Correct 22 ms 16068 KB Output is correct
18 Correct 25 ms 16112 KB Output is correct
19 Correct 20 ms 16072 KB Output is correct
20 Correct 19 ms 16120 KB Output is correct
21 Correct 21 ms 16068 KB Output is correct
22 Correct 20 ms 15996 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 476 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 3 ms 592 KB Output is correct
9 Correct 2 ms 464 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 2 ms 464 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 2 ms 540 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 26116 KB Output is correct
2 Correct 242 ms 26092 KB Output is correct
3 Correct 286 ms 26188 KB Output is correct
4 Correct 253 ms 26196 KB Output is correct
5 Correct 247 ms 26112 KB Output is correct
6 Correct 284 ms 33832 KB Output is correct
7 Correct 274 ms 31368 KB Output is correct
8 Correct 269 ms 30072 KB Output is correct
9 Correct 263 ms 28628 KB Output is correct
10 Correct 243 ms 26132 KB Output is correct
11 Correct 252 ms 26328 KB Output is correct
12 Correct 275 ms 26196 KB Output is correct
13 Correct 284 ms 26084 KB Output is correct
14 Correct 238 ms 25864 KB Output is correct
15 Correct 235 ms 25324 KB Output is correct
16 Correct 134 ms 23092 KB Output is correct
17 Correct 188 ms 27320 KB Output is correct
18 Correct 174 ms 27280 KB Output is correct
19 Correct 204 ms 27556 KB Output is correct
20 Correct 184 ms 27384 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 464 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 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 444 KB Output is correct
11 Correct 1 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 488 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 1 ms 480 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 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 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 464 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 26140 KB Output is correct
2 Correct 260 ms 26172 KB Output is correct
3 Correct 234 ms 22308 KB Output is correct
4 Correct 172 ms 19132 KB Output is correct
5 Correct 144 ms 16444 KB Output is correct
6 Correct 139 ms 15532 KB Output is correct
7 Correct 142 ms 14972 KB Output is correct
8 Correct 121 ms 14460 KB Output is correct
9 Correct 121 ms 14260 KB Output is correct
10 Correct 122 ms 14140 KB Output is correct
11 Correct 117 ms 13704 KB Output is correct
12 Correct 113 ms 13660 KB Output is correct
13 Correct 105 ms 13756 KB Output is correct
14 Correct 111 ms 15544 KB Output is correct
15 Correct 210 ms 27212 KB Output is correct
16 Correct 209 ms 25528 KB Output is correct
17 Correct 198 ms 24192 KB Output is correct
18 Correct 200 ms 22976 KB Output is correct
19 Correct 166 ms 19136 KB Output is correct
20 Correct 210 ms 19132 KB Output is correct
21 Correct 171 ms 19124 KB Output is correct
22 Correct 149 ms 18492 KB Output is correct
23 Correct 134 ms 17676 KB Output is correct
24 Correct 173 ms 22540 KB Output is correct
25 Correct 171 ms 22584 KB Output is correct
26 Correct 162 ms 20324 KB Output is correct
27 Correct 159 ms 20292 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 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 324 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 208 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 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 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 0 ms 204 KB Output is correct
27 Correct 1 ms 208 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 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 1 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 324 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 208 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 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 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 0 ms 204 KB Output is correct
27 Correct 1 ms 208 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 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 -