제출 #1188217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188217		irmuun	철인 이종 경기 (APIO18_duathlon)	C++20	100 / 100	62 ms	28604 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=1e5+5;

int n,m,now=0,cnt,num;
int tin[N],low[N],sz[2*N],wgh[2*N];
vector<int>g[N],f[2*N],stk;
ll ans=0;

void Tarjan(int u){
    low[u]=tin[u]=++now;
    stk.pb(u);
    num++;
    for(int v:g[u]){
        if(tin[v]==0){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]==tin[u]){
                cnt++;
                wgh[cnt]=0;
                for(int x=0;x!=v;){
                    x=stk.back();
                    f[cnt].pb(x);
                    f[x].pb(cnt);
                    stk.pop_back();
                    wgh[cnt]++;
                }
                f[cnt].pb(u);
                f[u].pb(cnt);
                wgh[cnt]++;
            }
        }
        else{
            low[u]=min(low[u],tin[v]);
        }
    }
}

void dfs(int u,int p){
    sz[u]=(u<=n);
    for(int v:f[u]){
        if(v!=p){
            dfs(v,u);
            ans+=2ll*wgh[u]*sz[u]*sz[v];
            sz[u]+=sz[v];
        }
    }
    ans+=2ll*wgh[u]*sz[u]*(num-sz[u]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    fill(wgh+1,wgh+n+1,-1);
    cnt=n;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i=1;i<=n;i++){
        if(tin[i]==0){
            num=0;
            Tarjan(i);
            stk.pop_back();
            dfs(i,0);
        }
    }
    cout<<ans;
}

• 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