Submission #1293616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293616		dwuy	Duathlon (APIO18_duathlon)	C++20	100 / 100	69 ms	31560 KiB

count_triplets

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MX = 200005;
int n, m, bcc;
int num[MX], low[MX];
long long sz[MX], f[MX][3];
vector<int> G[MX];
vector<int> T[MX];

void buildBCT(int u){
    static int peak = 0;
    static stack<int> st;
    num[u] = low[u] = ++peak;
    st.push(u);
    for(int v: G[u]){
        if(!num[v]){
            buildBCT(v);
            low[u] = min(low[u], low[v]);
            if(low[v] == num[u]){
                bcc++;
                T[u].push_back(n + bcc);
                do{
                    sz[n + bcc]++;
                    T[n + bcc].emplace_back(st.top());
                    st.pop();
                } while(T[n + bcc].back() != v);
            }
        }
        else low[u] = min(low[u], num[v]);
    }
}

long long c2(int x){
    return 1LL * x * (x - 1) / 2;
}

long long c3(int x){
    return 1LL * x * (x - 1) * (x - 2) / 6;
}

long long solve(int u){
    static long long ans = 0;
    if(u <= n) f[u][1] += 1;
    for(int v: T[u]){
        solve(v);
        ans += f[u][1] * f[v][2] + f[u][2] * f[v][1];
        f[u][1] += f[v][1];
        f[u][2] += f[v][2];
        if(u <= n) f[u][2] += f[v][1];
        else f[u][2] += f[v][1] * (sz[u] - 1);
    }
    return ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for(int i=1; i<=m; i++){
        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]){
        buildBCT(i);
        solve(i);
    }
    cout << solve(0) * 2;

    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