Submission #721866

#	Time	Username	Problem	Language	Result	Execution time	Memory
721866		Son	Duathlon (APIO18_duathlon)	C++14	100 / 100	125 ms	28204 KiB

count_triplets

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

int n,m;
vector < int > E[100005];
int low[100005], num[100005];
int idx = 0;
vector < int > bcc_group[200005];
int bccs = 1;
vector < int > stck;
int N = 0, sub[200005];
LL ans = 0;

void dfs1( int u, int p ){
    low[u] = num[u] = ++idx;
    stck.pb(u);
    N++;
    for ( int v : E[u] ){
        if ( num[v] ) low[u] = min( low[u], num[v] );
        else {
            dfs1(v,u);
            low[u] = min(low[u], low[v]);
            if ( low[v] >= num[u] ){
                bcc_group[u].pb(n + bccs);
                while ( !bcc_group[n+bccs].size() || bcc_group[n+bccs].back() != v ){
                    bcc_group[n+bccs].pb(stck.back());
                    stck.pop_back();
                }
                bccs++;
            }
        }
    }
}

void dfs2( int u ){
    sub[u] = (u <= n);
    for ( int v : bcc_group[u] ){
        dfs2(v);
        sub[u] += sub[v];
        if ( u > n ) ans -= bcc_group[u].size() * 1LL * (sub[v]) * (sub[v]-1);
    }

    if (u > n){
        ans -= bcc_group[u].size() * 1LL * (N-sub[u]) * (N - sub[u] - 1);
    }
}

int main(){

    scanf("%d%d",&n,&m);
    for ( int i = 1; i <= m; i++ ){
        int u , v;
        scanf("%d%d",&u,&v);
        E[u].pb(v);
        E[v].pb(u);
    }

    for ( int i = 1; i <= n; i++ ){
        if ( num[i] == 0 ){
            N = 0;
            dfs1(i,-1);
            ans += N * 1LL * (N-1) * (N-2);
            dfs2(i);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

• 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