제출 #1268275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268275		Sofiatpc	철인 이종 경기 (APIO18_duathlon)	C++20	0 / 100	66 ms	27976 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], nxt;
ll ans, sub[2*MAXN], n;

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){
    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 == 1 && f > 1) || (s != 1 && 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])*(n-sub[viz] -(s<=n) );
        sub[s] += sub[viz];
    }

    ans += val*(n-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);
    }

    dist[1] = 1;
    dfs(1,0);

    nxt = n+1;
    c[1] = nxt++;
    dfs2(1);

    dfsbl(1,0);

    cout<<ans<<"\n";
}

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