제출 #710666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710666		Stickfish	철인 이종 경기 (APIO18_duathlon)	C++17	0 / 100	1094 ms	1048576 KiB

count_triplets

#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
using ll = long long;

const int MAXN = 1e5 + 23;
vector<int> edg[MAXN];
int depth[MAXN];
int tin[MAXN];
int fup[MAXN];
int timer = 0;
bitset<MAXN> used;

vector<int> stck;
vector<int> comps[MAXN];
vector<int> cedg[MAXN];
int csz[MAXN];
int compcnt = 0;
int rcomps[MAXN];

void dfs(int v, int rt) {
    used[v] = 1;
    tin[v] = fup[v] = timer++;
    stck.push_back(v);
    for (auto u : edg[v]) {
        if (u == rt)
            continue;
        if (used[u]) {
            fup[v] = min(fup[v], tin[u]);
            continue;
        }
        dfs(u, v);
        fup[v] = min(fup[v], fup[u]);
        if (fup[u] > tin[v]) {
            while (stck.back() != v) {
                comps[compcnt].push_back(stck.back());
                rcomps[stck.back()] = compcnt;
                stck.pop_back();
            }
            ++compcnt;
        }
    }
}

void cdfs(int v, int rt) {
    csz[v] = comps[v].size();
    for (auto u : cedg[v]) {
        if (u == rt)
            continue;
        cdfs(u, v);
        csz[v] += csz[u];
    }
}

signed main() {
    int n, m; 
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }
    dfs(0, 0);
    while (stck.size()) {
        comps[compcnt].push_back(stck.back());
        rcomps[stck.back()] = compcnt;
        stck.pop_back();
    }
    ++compcnt;
    for (int v = 0; v < n; ++v) {
        for (auto u : edg[v]) {
            if (rcomps[v] != rcomps[u])
                cedg[rcomps[v]].push_back(rcomps[u]);
        }
    }
    cdfs(0, 0);
    //cout << compcnt << endl;
    //for (int i = 0; i < compcnt; ++i)
        //cout << comps[i].size() << ' ';
    //cout << endl;
    //cout << endl;
    ll ans = 1ll * n * (n - 1) * (n - 2);
    for (int v = 0; v < compcnt; ++v) {
        for (auto u : cedg[v]) {
            if (csz[u] > csz[v])
                continue;
            //cout << comps[v].size() << ' ' << csz[u] << endl;
            ans -= 1ll * csz[u] * (csz[u] - 1) * comps[v].size();
            ans -= 2ll * csz[u] * (comps[v].size() - 1);
        }
        
        ans -= 1ll * (n - csz[v]) * (n - csz[v] - 1) * comps[v].size();
        ans -= 2ll * (n - csz[v]) * (comps[v].size() - 1);
        //cout << "!" << comps[v].size() << ' ' << n - csz[v] << endl;
    }
    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