Submission #1143982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143982		CSQ31	Duathlon (APIO18_duathlon)	C11	Compilation error	0 ms	0 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 2e5+5;
struct edges{
    int v,id;
    edges(int _v,int _id):v(_v),id(_id){}
    edges(){}
};

vector<edges>adj[MAXN];
vector<int>g[MAXN]; //edges of the block cut tree
int depth[MAXN],low[MAXN],visited[MAXN],art[MAXN];
int bcc = 0; //intialize this to n
int num = 0;
stack<int>bcc_nodes;
void dfs(int u,int p,int root){
    num++;
    int child_cnt = 0;
    bcc_nodes.push(u);
    visited[u] = 1;
    low[u] = depth[u];

    for(auto [v,id]:adj[u]){
        if(id == p)continue; 

        if(visited[v])low[u] = min(low[u],depth[v]);
        else{
            child_cnt++;
            depth[v] = depth[u] + 1;
            dfs(v,id,root);
            low[u] = min(low[u],low[v]);

            if(low[v] >=  depth[u]){
                bcc++;
                g[u].push_back(bcc);
                g[bcc].push_back(u);

                while(bcc_nodes.top() != u){
                    int x = bcc_nodes.top();
                    g[x].push_back(bcc);
                    g[bcc].push_back(x);
                    bcc_nodes.pop();

                }

            }
        }
    }

}

int sub[MAXN],n;
ll ans = 0;
void dfs2(int v,int u){
    sub[v] = v<=n;
    for(int x:g[v]){
        if(x==u)continue;
        dfs2(x,v);
        sub[v] += sub[x];
    }
    if(v<=n)return;
    ll sum = 0;
    for(int x:g[v]){
        if(x==u)sum += (num-sub[v]) * 1LL * (num-sub[v]-1);
        else sum += sub[x] * 1LL * (sub[x]-1);
    }
    
    for(int x:g[v]){
        if(x==u)sum -= (num-sub[v]) * 1LL * (num-sub[v]-1);
        else sum -= sub[x] * 1LL * (sub[x]-1);

        ans-=sum;

        if(x==u)sum += (num-sub[v]) * 1LL * (num-sub[v]-1);
        else sum += sub[x] * 1LL * (sub[x]-1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int m;
    cin>>n>>m;
    bcc = n;
    for(int i=0;i<m;i++){
        int v,u;
        cin>>v>>u;
        adj[v].push_back({u,i});
        adj[u].push_back({v,i});
    }
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        num = 0;
        dfs(i,-1,i);
        ans += 1LL *  num * (num-1) * (num-2);
        dfs2(i,-1);
    }
    cout<<ans<<'\n';



}

Compilation message (stderr)

count_triplets.c:1:10: fatal error: bits/stdc++.h: No such file or directory
    1 | #include <bits/stdc++.h>
      |          ^~~~~~~~~~~~~~~
compilation terminated.