Submission #1271392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271392		SpyrosAliv	Duathlon (APIO18_duathlon)	C++20	0 / 100	1 ms	584 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
#define int long long

// make articulation tree
// w_u * (w_u - 1) * (w_u - 2) + w_u * (w_u - 1) * (n - w_u) * 2

const int MN = 20;
vector<vector<int>> g(MN);
vector<vector<int>> tree(MN);
int n, m, ans = 0;
vector<bool> art(MN, false), vis(MN, false);
vector<int> low(MN, 0), dep(MN, 0), below(MN, 0);
int t = 0, tot = 0;
int par[MN], sz[MN];

int find(int u) {
    if (par[u] == u) return u;
    return par[u] = find(par[u]);
}

void merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    if (sz[u] > sz[v]) swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
}

void dfs(int node, int p = 0) {
    vis[node] = true;
    dep[node] = dep[p] + 1;
    low[node] = dep[node];
    int ch = 0;
    for (auto next: g[node]) {
        if (next == p) continue;
        if (dep[next] != 0) {
            low[node] = min(low[node], dep[next]);
            continue;
        }
        ch++;
        dfs(next, node);
        low[node] = min(low[node], low[next]);
        if (low[next] >= dep[node]) art[node] = true;
    }
    if (g[node].size() == 1) art[node] = true;
    if (dep[node] == 1 && ch > 1) art[node] = true;
    else if (dep[node] == 1 && ch == 1) art[node] = false;
}

void get_below(int node, int par = 0) {
    assert(below[node] == 0);
    below[node] = sz[node];
    for (auto next: tree[node]) {
        if (next == par) continue;
        get_below(next, node);
        below[node] += below[next];
    }
}

void dfs2(int node, int par, int tot) {
    assert(vis[node] == false);
    vis[node] = true;
    ans += 2 * sz[node] * (sz[node] - 1) * (tot - sz[node]);
    vector<int> subs;
    int ss = 0;
    for (auto next: tree[node]) {
        if (next == par) continue;
        subs.push_back(below[next]);
        ss += below[next];
    }
    subs.push_back(tot - below[node]);
    ss += subs.back();
    for (auto v: subs) {
        ans += v * (ss - v);
    }
    subs.clear();
    for (auto next: tree[node]) {
        if (next == par) continue;
        dfs2(next, node, tot);
    }
}

void get_ans(int root) {
    get_below(root);
    tot = below[root];
    dfs2(root, 0, tot);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        sz[i] = 1;
        par[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (art[i]) continue;
        for (auto next: g[i]) {
            if (art[next]) continue;
            merge(i, next);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (find(i) != i || art[i]) continue;
        ans += sz[i] * (sz[i] - 1) * (sz[i] - 2); 
    }
    for (int i = 1; i <= n; i++) {
        if (!art[i]) continue;
        set<int> conn;
        for (auto next: g[i]) {
            if (art[next] && next < i) continue;
            conn.insert(find(next));
        }
        for (auto v: conn) {
            tree[i].push_back(v);
            tree[v].push_back(i);
        }
    }
    vis.assign(n+1, false);
    for (int i = 1; i <= n; i++) {
        if (vis[i] || find(i) != i) continue;
        get_ans(find(i));
    }
    cout << ans << "\n";
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10