Submission #1143988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143988		CSQ31	Duathlon (APIO18_duathlon)	C++20	100 / 100	68 ms	29508 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
ll 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(g[bcc].back() != v){
                    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);
    }
    ans -= sum * (g[v].size()-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';



}

• 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