제출 #958594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958594		rxlfd314	Duathlon (APIO18_duathlon)	C++17	100 / 100	83 ms	31628 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for (int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N,M;
  cin>>N>>M;
  vt<vt<int>> adj(N);
  FOR(_,1,M){
    int a,b;
    cin>>a>>b;
    adj[--a].push_back(--b);
    adj[b].push_back(a);
  }
  ll ans=0;
  vt<int> tin(N,-1),low(N),szs(N<<1);
  vt<vt<int>> bcc_adj(N<<1);
  int B=0;
  FOR(r,0,N-1){
    if(tin[r]>=0)
      continue;
    int n=0,timer=0;
    vt<int> rem;
    function<void(int,int)> find_bccs=[&](int i,int p){
      n++;
      low[i]=tin[i]=timer++;
      rem.push_back(i);
      for(int j:adj[i]){
        if(j==p)
          continue;
        if(tin[j]>=0)
          low[i]=min(low[i],tin[j]);
        else{
          find_bccs(j,i);
          low[i]=min(low[i],low[j]);
          if(low[j]>=tin[i]){
            bcc_adj[i].push_back(B+N);
            while(!size(bcc_adj[B+N]) || bcc_adj[B+N].back()!=j){
              bcc_adj[B+N].push_back(rem.back());
              rem.pop_back();
            }
            B++;
          }
        }
      }
    };
    find_bccs(r,r);
    ans+=1ll*n*(n-1)*(n-2);
    function<void(int)> dfs=[&](int i){
      szs[i]=i<N;
      for(int j:bcc_adj[i]){
        dfs(j);
        szs[i]+=szs[j];
        if(i>=N)
          ans-=1ll*size(bcc_adj[i])*szs[j]*(szs[j]-1);
      }
      if(i>=N)
        ans-=1ll*size(bcc_adj[i])*(n-szs[i])*(n-szs[i]-1);
    };
    dfs(r);
  }
  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