Submission #1293526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293526		dwuy	Duathlon (APIO18_duathlon)	C++20	0 / 100	61 ms	24080 KiB

count_triplets

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

const int MX = 400005;
int n, m, bcc;
int num[MX], low[MX];
int 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]);
    }
}

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

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

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

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    system("cls");
    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);
    }

    buildBCT(1);
    cout << solve(1) * 2;

    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:65:11: warning: ignoring return value of 'int system(const char*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     system("cls");
      |     ~~~~~~^~~~~~~

• 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