Submission #1204161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204161		Ghulam_Junaid	Duathlon (APIO18_duathlon)	C++17	100 / 100	122 ms	27596 KiB

count_triplets

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

const int N = 2e5 + 100;
int n, m, h[N], mnh[N], sub[N], bccs;
vector<int> g[N], tg[N], st;
long long ans;

void get_sz(int v, int p = 0){
    sub[v] = (v <= n);
    for (int u : tg[v]){
        if (u == p) continue;
        // cout << v << " to " << u << endl;
        get_sz(u, v);
        sub[v] += sub[u];
    }
}

void dfs(int v, int p = 0){
    mnh[v] = h[v] = h[p] + 1;
    st.push_back(v);

    for (int u : g[v]){
        if (u == p){
            p = -1;
            continue;
        }

        if (h[u]){
            mnh[v] = min(mnh[v], h[u]);
            continue;
        }

        dfs(u, v);
        mnh[v] = min(mnh[v], mnh[u]);

        if (mnh[u] >= h[v]){
            // cout << v << " -bcc- " << u << endl; 
            bccs++;
            tg[v].push_back(n + bccs);
            tg[n + bccs].push_back(st.back());
            st.pop_back();
            while (tg[n + bccs].back() != u){
                tg[n + bccs].push_back(st.back());
                st.pop_back();
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i ++){
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int v = 1; v <= n; v ++){
        if (h[v]) continue;
        int prv = bccs;
        dfs(v);
        get_sz(v);
        ans += 1ll * sub[v] * (sub[v] - 1) * (sub[v] - 2);

        for (int i = prv + 1; i <= bccs; i ++){
            int u = i + n;
            ans -= 1ll * (tg[u].size()) * (sub[v] - sub[u]) * (sub[v] - sub[u] - 1);
            for (int c : tg[u])
                ans -= 1ll * (tg[u].size()) * (sub[c]) * (sub[c] - 1);
        }
    }
    cout << ans << endl;
}

• 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