Submission #559998

#	Time	Username	Problem	Language	Result	Execution time	Memory
559998		hoanghq2004	Duathlon (APIO18_duathlon)	C++14	100 / 100	163 ms	37508 KiB

count_triplets

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 10;

int n, m;
vector <int> e[N], g[N];
vector <int> stk;
int num[N], low[N], ti, cnt, comp[N], a[N], sz[N];
long long ans;

void dfs(int u, int p) {
    num[u] = low[u] = ++ti;
    stk.push_back(u);
    for (auto v: g[u]) {
        if (v == p) continue;
        if (!num[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= num[u]) {
                ++cnt;
                while (1) {
                    int w = stk.back();
                    stk.pop_back();
                    e[cnt + n].push_back(w);
                    e[w].push_back(cnt + n);
                    if (w == v) break;
                }
                e[cnt + n].push_back(u);
                e[u].push_back(cnt + n);
            }
        } else low[u] = min(low[u], num[v]);
    }
}

int init(int u, int p) {
    int ans = (u <= n);
    for (auto v: e[u]) {
        if (v == p) continue;
        ans += init(v, u);
    }
    return ans;
}

void solve(int u, int p, int m) {
    sz[u] = (u <= n);
    for (auto v: e[u]) {
        if (v == p) continue;
        solve(v, u, m);
        sz[u] += sz[v];
    }
    if (u <= n) return;
    vector <int> tmp;
    for (auto v: e[u]) {
        if (v == p) tmp.push_back(m - sz[u]);
        else tmp.push_back(sz[v]);
    }
    for (auto x: tmp) ans -= 1LL * x * (x - 1) * (e[u].size() - 1);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) if (!num[i]) dfs(i, 0);
    for (int u = 1; u <= n; ++u)
        for (auto v: g[u])
            if (comp[u] != comp[v])
                e[u].push_back(v);
    for (int i = 1; i <= n; ++i) if (!sz[i]) {
        int m = init(i, 0);
        ans += 1LL * m * (m - 1) * (m - 2);
        solve(i, 0, m);
    }
    cout << ans;
}

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