Submission #393573

#	Time	Username	Problem	Language	Result	Execution time	Memory
393573		KoD	Duathlon (APIO18_duathlon)	C++17	71 / 100	286 ms	33832 KiB

count_triplets

#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 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10