Submission #111605

#	Time	Username	Problem	Language	Result	Execution time	Memory
111605		sealnot123	Duathlon (APIO18_duathlon)	C++14	23 / 100	200 ms	39380 KiB

count_triplets

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define ep emplace_back
#define sz(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const int N=100050;
vector< vector<int> > comp; // bridge tree
vector<int> g[N],G[N],sta;
int t,art[N],visited[N],lowlink[N],mk[N],ncomp[N];
LL dp[2][N],ans=0;
void dfs(int u, int p){
    visited[u] = lowlink[u] = ++t;
    sta.pb(u);
    for(int e : g[u]){
        if(e==p) continue;
        if(!visited[e]){
            dfs(e, u);
            lowlink[u] = min(lowlink[u], lowlink[e]);
        }else{
            lowlink[u] = min(lowlink[u], visited[e]);
        }
    }
    if(lowlink[u] == visited[u]){
        int nw = comp.size();
        comp.pb({u});
        ncomp[u]=nw;
        while(sta.back()!=u){
            comp.back().pb(sta.back());
            ncomp[sta.back()]=nw;
            sta.pop_back();
        }
        sta.pop_back();
    }
}
void DFS(int u, int p){
    LL S = sz(comp[u]);
    for(int e : G[u]){
        if(e==p) continue;
        DFS(e,u);
        ans += dp[0][e]*dp[1][u];
        ans += dp[1][e]*dp[0][u];
        dp[0][u] += dp[0][e];
        dp[1][u] += dp[1][e] + dp[0][e]*S;
        ans += dp[0][e]*(S-1)*(S-1);
        ans += dp[1][e]*S;
    }
    dp[0][u] += S;
    dp[1][u] += (S-1)*(S-1);
//    printf("%lld %lld %lld %lld===\n",ans,S,dp[0][u],dp[1][u]);
}
int main(){
//    freopen("104","r",stdin);
//    freopen("104.sol","w",stdout);
    int n,m,i,j,a,b;
    scanf(" %d %d",&n,&m);
    for(i=1;i<=m;i++){
        scanf(" %d %d",&a,&b);
        g[a].pb(b); g[b].pb(a);
    }
    dfs(1,1);
    for(i=1;i<=n;i++){
        if(!visited[i]) dfs(i,i);
    }
    for(i=0;i<sz(comp);i++){
//        printf("#%d: ",i);
        for(int u : comp[i]){
//            printf("%d ",u);
            for(int e : g[u]){
                if(ncomp[e]!=i) mk[ncomp[e]]=1;
            }
        }
        for(int u : comp[i]){
            for(int e : g[u]){
                if(mk[ncomp[e]]) G[i].pb(ncomp[e]),mk[ncomp[e]]=0;
            }
        }
//        printf("\n");
    }
    for(i=1;i<=n;i++){
        if(!dp[0][i]) DFS(i,i);
    }
    ans<<=1;
    for(i=0;i<sz(comp);i++){
        LL S = sz(comp[i]);
        ans += S*(S-1)*(S-2);
    }
    printf("%lld",ans);
    return 0;
}
/*
4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2
*/

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:58:15: warning: unused variable 'j' [-Wunused-variable]
     int n,m,i,j,a,b;
               ^
count_triplets.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10