제출 #569064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569064		Ooops_sorry	철인 이종 경기 (APIO18_duathlon)	C++14	100 / 100	248 ms	40172 KiB

count_triplets

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld double
#define ll long long

mt19937 rnd(51);

const int N = 1e5 + 10, M = 2e5 + 10, K = 3e5 + 10;
int cnt = 0, n, m, total;
vector<int> tin(N), fup(N), arr, sz(K), gr[K];
vector<pair<int,int>> g[N], gt[N];
vector<bool> used(K), was(M), vis(N);
deque<int> q;
ll ans = 0;

void dfs(int v, int p) {
    used[v] = 1;
    tin[v] = fup[v] = cnt++;
    for (auto to : g[v]) {
        if (to.first == p) continue;
        if (used[to.first]) {
            fup[v] = min(fup[v], tin[to.first]);
            if (tin[to.first] < tin[v]) {
                gt[v].pb(to);
            }
        } else {
            if (p == -1) {
                q.pb(to.second);
                was[to.second] = 1;
            }
            dfs(to.first, v);
            gt[v].pb(to);
            fup[v] = min(fup[v], fup[to.first]);
        }
    }
}

void zhfs(int v) {
    if (vis[v]) return;
    vis[v] = 1;
    for (auto to : gt[v]) {
        if (was[to.second]) continue;
        was[to.second] = 1;
        if (fup[to.first] < tin[v]) {
            arr.pb(to.second);
            zhfs(to.first);
        } else {
            q.pb(to.second);
        }
    }
}

void gfs(int v, int p) {
    used[v] = 1;
    if (v < n) {
        sz[v] = 1;
    }
    for (auto to : gr[v]) {
        if (to != p) {
            gfs(to, v);
            sz[v] += sz[to];
        }
    }
}

void walk(int v, int p) {
    int up = total - sz[v];
    if (v >= n) {
        int k = gr[v].size();
        ans -= (ll)up * (up - 1) * (k - 1);
        for (auto to : gr[v]) {
            if (to != p) {
                ans -= (ll)sz[to] * (sz[to] - 1) * (k - 1);
            }
        }
    }
    for (auto to : gr[v]) {
        if (to != p) {
            walk(to, v);
        }
    }
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    vector<pair<int,int>> e(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        e[i] = {u, v};
        g[u].pb({v, i});
        g[v].pb({u, i});
    }
    int now = n;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            int was_cnt = cnt;
            dfs(i, -1);
            int dif = cnt - was_cnt;
            ans += (ll)dif * (dif - 1) * (dif - 2);
            while (q.size() > 0) {
                int j = q.front();
                q.pop_front();
                arr.clear();
                arr.pb(j);
                zhfs(e[j].first);
                zhfs(e[j].second);
                set<int> st;
                for (auto j : arr) {
                    st.insert(e[j].first);
                    st.insert(e[j].second);
                }
                for (auto to : st) {
                    gr[to].pb(now);
                    gr[now].pb(to);
                }
                now++;
            }
        }
    }
    fill(used.begin(), used.end(), 0);
    for (int i = n; i < now; i++) {
        if (!used[i]) {
            gfs(i, -1);
            total = sz[i];
            walk(i, -1);
        }
    }
    cout << ans << endl;
    return 0;
}

• 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