Submission #1061983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061983		AlperenT_	Duathlon (APIO18_duathlon)	C++17	100 / 100	99 ms	60104 KiB

count_triplets

#include <bits/stdc++.h>
 
#pragma GCC optimize("unroll-loops","O3")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ld long double 
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
const int maxn = 5e5 + 10 , maxq = 1e5 , lg = 22 , sq = 333   , inf = 1e9 +100 , maxk = 2022 , mod = 998244353;
int n ,m ,ans = 0 , c =0   , dis[maxn] , cnt  , mx[maxn]  , m1[maxn] , m2[maxn]   ,w[maxn], sb[maxn]  ;
vector <int >G[maxn] ;
vector <int> st , N[maxn] ; 
void d1(int v , int p =0 ){
    c+= (v<=n) ;;
    m1[v] =1  ;
    for(int u : N[v]){
        if(u == p)continue ; 
        d1(u,v) ; 
    }
}
void add(int v, int u){
    N[v].pb(u) ;
    N[u].pb(v) ; 
}

void d2(int v){
    m2[v] = 1 ;
    mx[v] = dis[v] ;
    for(int u : G[v]){
        if(m2[u] == 1){
            mx[v] = min(mx[v] , dis[u]) ; 
            continue ; 
        }
        int ls = st.back() ; 
        dis[u] = dis[v] + 1; 
        d2(u) ;
        mx[v] = min(mx[v] ,mx[u]) ;
        if(mx[u] == dis[v]){
            add(cnt ,v) ;
            while(st.back() != ls){
                add(cnt , st.back()) ;
                st.pop_back() ; 
            }
            cnt++ ;
        } 
    }
    st.pb(v) ;
}
void dfs(int v ,int p =0){
    sb[v] = (v <= n) ; 
    for(int u : N[v]){
        if(u == p)continue ;
        dfs(u ,v) ;
        sb[v] += sb[u] ; 
    }
    int sm =0 ;
    sm += c*(c-1)/2 ;
    for(int u : N[v]){
        if(u == p){
            int x = c-sb[v] ; 
            sm-= x*(x-1)/2 ;
        }else{
            sm -= sb[u]*(sb[u]-1)/2 ; 
        }
    }
    ans += sm * w[v] ;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); 
    cin >> n >> m ;
    cnt = n+1 ; 
    rep(i,1,m){
        int v , u ;
        cin >> v >> u ; 
        G[v].pb(u) ;
        G[u].pb(v) ;
    }
    st.pb(0) ; 
    rep(i ,1, n){
        if(m2[i] == 1)continue ;
        d2(i) ;
    }
    rep(i ,1 ,2*n){
        if(i <= n)w[i] = -1 ;
        else w[i] = sz(N[i]) ; 
    }
    rep(i ,1 ,2*n){
        if(m1[i] == 1)continue ; 
        c =0 ;
        d1(i) ; 
        if(c == 0)continue ; 
       dfs(i) ; 
    }
    cout << ans*2 << "\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