제출 #1268281

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

count_triplets

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAXN = 1e5+5, MAX = 16;
vector<int> adj[MAXN], bl[2*MAXN];
int dist[MAXN], low[MAXN], c[MAXN], rz, nxt, n;
ll ans, sub[2*MAXN], tam;

void dfs(int s, int p){
    low[s] = dist[s];

    for(int viz : adj[s]){
        if(viz == p)continue;

        if(dist[viz])low[s] = min(low[s],dist[viz]);
        else{
            dist[viz] = dist[s]+1;
            dfs(viz,s);
            low[s] = min(low[s],low[viz]);
        }
    }
}

void dfs2(int s){
    tam++;
    bl[c[s]].push_back(s); bl[s].push_back(c[s]);

    int f = 0;
    for(int viz : adj[s]){
        if(c[viz])continue;
        f++;

        if( (s == rz && f > 1) || (s != rz && low[viz] >= dist[s])){
            bl[nxt].push_back(s); bl[s].push_back(nxt);
            c[viz] = nxt++;
        }else c[viz] = c[s];
        dfs2(viz);
    }
}

void dfsbl(int s, int p){
    ll val;
    if(s <= n)val = 1;
    else val = bl[s].size()-2;

    for(int viz : bl[s]){
        if(viz == p)continue;
        
        dfsbl(viz,s);
        ans += val*(sub[viz])*(tam-sub[viz] -(s<=n) );
        sub[s] += sub[viz];
    }

    ans += val*(tam-sub[s] -(s<=n) )*sub[s];

    if(s <= n)sub[s]++;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int m; cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int a,b; cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for(int i = 1; i <= n; i++)
        if(dist[i] == 0){
            dist[i] = 1;
            dfs(i,0);
        }

    nxt = n+1;
    for(int i = 1; i <= n; i++)
        if(c[i] == 0){
            rz = i;
            c[i] = nxt++;
            tam = 0;
            dfs2(i);

            dfsbl(i,0);
        }
    
    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