제출 #1160972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160972		crafticat	철인 이종 경기 (APIO18_duathlon)	C++20	0 / 100	46 ms	25240 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = (n); i >= 0; i--)

template<typename T>
using V = vector<T>;
using vi = vector<int>;
using ll = long long;

struct DSU
{
    vi p;
    vi siz;
    int comp;

    DSU(int n)
    {
        p.resize(n, -1);
        siz.resize(n, 1);
        comp = n - 1;
    }

    int get(int x)
    {
        if (p[x] == -1) return x;
        return p[x] = get(p[x]);
    }

    void unite(int x, int y)
    {
        x = get(x); y = get(y);
        if (x == y) return;
        siz[x] += siz[y];
        p[y] = x;
        comp--;
    }
};

V<vi> g;
vi vis;
vi crits;
vi minH, dep;

void findCrits(int x, int p,bool root = true, int d = 0)
{
    dep[x] = d;
    vis[x] = 1;
    int child = 0;

    for (auto y : g[x])
    {
        if (vis[y] == 2) continue;
        if (vis[y] == 1)
        {
            if (y == p) continue;
            minH[x] = min(minH[x], dep[y]);
            continue;
        }
        findCrits(y, x, false, d + 1);
        child++;

        minH[x] = min(minH[x], minH[y]);
    }

    if (root and child > 1)
        crits.push_back(minH[x]);
    if (!root and minH[x] >= dep[x] and child > 0)
        crits.push_back(x);

    vis[x] = 2;
}

DSU *dsu;

void dfs(int x)
{
    vis[x] = 1;
    for (auto y : g[x])
    {
        if (vis[y]) continue;
        dfs(y);
        dsu->unite(x, y);
    }
}

ll computeSiz(int x, const V<vi> &tree, const vi &siz)
{
    ll ans = siz[x];
    vis[x] = 1;
    for (auto y : tree[x])
    {
        if (vis[y] == 1) continue;
        ans += computeSiz(y, tree, siz);
    }
    return ans;
}

ll solveTree(int x, int p, const V<vi> &tree, const vi &siz, vi &prefixSiz, int globalSum)
{
    ll ans = 0;
    vis[x] = 2;
    prefixSiz[x] = siz[x];
    vi sizes;

    for (auto y : tree[x])
    {
        if (vis[y] == 2) continue;
        ans += solveTree(y, x, tree, siz, prefixSiz, globalSum);
        sizes.push_back(prefixSiz[y]);
        prefixSiz[x] += prefixSiz[y];

        if (siz[y] > 1)
            ans += siz[y] * (siz[y] - 1) + siz[y] * (prefixSiz[y] - siz[y]);
    }
    sizes.emplace_back(globalSum - prefixSiz[x]);

    F0R(i, sizes.size())
    {
        FOR(j,i + 1,sizes.size())
        {
            ans += sizes[i] * sizes[j] * 2 * siz[x];
        }
    }

    if (siz[x] > 2) ans += max(siz[x] * (siz[x] - 1) * (siz[x] -2), 0);
    if (siz[x] >1 ) ans += max(siz[x] * (siz[x] - 1), 0) * (globalSum - siz[x]) * 2;

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, m; cin >> n >> m;
    g.resize(n + 1);
    vis.resize(n + 1);
    dep.resize(n + 1);
    minH.resize(n + 1, 1e9);

    F0R(i, m)
    {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    FOR(i, 1, n + 1)
    {
        if (vis[i] == 0)
            findCrits(i, -1);
    }

    vis.assign(n + 1, 0);

    for (auto c : crits)
        vis[c] = 1;
    dsu = new DSU(n + 1);

    FOR(i, 1, n + 1)
    {
        if (vis[i]) continue;
        dfs(i);
    }

    V<vi> tree(dsu->comp);
    vi mapTo(n + 1, -1);
    vi siz(dsu->comp);
    int nextId = 0;

    for (auto c : crits)
    {
        for (auto y : g[c])
        {
            y = dsu->get(y);
            c = dsu->get(c);

            if (mapTo[y] == -1) mapTo[y] = nextId++;
            if (mapTo[c] == -1) mapTo[c] = nextId++;
            siz[mapTo[y]] = dsu->siz[y];
            siz[mapTo[c]] = dsu->siz[c];

            tree[mapTo[y]].push_back(mapTo[c]);
            tree[mapTo[c]].push_back(mapTo[y]);
        }
    }

    ll ans = 0;
    vis.assign(dsu->comp, 0);
    vi prefixSum(dsu->comp, 0);

    F0R(i, dsu->comp)
    {
        if (vis[i] == 0)
        {
            int globalSum = computeSiz(i, tree, siz);
            ans += solveTree(i, -1, tree, siz, prefixSum, globalSum);
        }
    }
    cout << n * (n - 1) * (n - 2) / 3 << '\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