Submission #1213349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213349		spike1236	Duathlon (APIO18_duathlon)	C++20	0 / 100	49 ms	30912 KiB

count_triplets

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

const int MAXN = 100'000;
const int MAXM = 200'000;

int n, m;

vector<int> g[MAXN];                
vector<int> T[MAXN + MAXM];         
int timer = 0, bcc_cnt = 0;
int tin[MAXN], low[MAXN];
int st[MAXN], top = 0;              

void dfs1(int u, int p) {
    tin[u] = low[u] = ++timer;
    st[top++] = u;

    for (int v : g[u]) {
        if (!tin[v]) {                          
            dfs1(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] >= tin[u]) {             
                int block = n + bcc_cnt++;      
                T[u].push_back(block);
                T[block].push_back(u);
                while (true) {
                    int x = st[--top];
                    T[x].push_back(block);
                    T[block].push_back(x);
                    if (x == v) break;
                }
            }
        }
        else if (v != p)                        
            low[u] = min(low[u], tin[v]);
    }
}

int64 comp_sz;                     
int64 answer = 0;
int64 sub_sz[MAXN + MAXM];         

void dfs2(int u, int parent, bool isRootBlock) {
    sub_sz[u] = (u < n);           

    for (int v : T[u]) if (v != parent) {
        dfs2(v, u, false);
        sub_sz[u] += sub_sz[v];

        if (u >= n) {              
            int deg = T[u].size();
            answer -= int64(deg - isRootBlock) * sub_sz[v] * (sub_sz[v] - 1);
        }
    }

    if (u >= n) {                  
        int deg = T[u].size();
        int64 rem = comp_sz - sub_sz[u];
        answer -= int64(deg) * rem * (rem - 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    while (m--) {
        int u, v;  cin >> u >> v;  --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 0; i < n; ++i) if (!tin[i]) {

        int old_bcc = bcc_cnt;
        timer = 0; top = 0;
        dfs1(i, -1);
        comp_sz = timer;                       

        answer += comp_sz * (comp_sz - 1) * (comp_sz - 2);

        dfs2(i, -1, true);

    }

    cout << answer << '\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