Submission #958365

#	Time	Username	Problem	Language	Result	Execution time	Memory
958365		rxlfd314	Duathlon (APIO18_duathlon)	C++17	0 / 100	68 ms	35320 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)

constexpr int mxN=100000;
int N,M;
vt<ari2> adj[mxN];

int tin[mxN],stin[mxN],timer;
bool bridge[mxN<<1];
vt<int> added;
void find_bridges(int i,int p) {
  stin[i]=tin[i]=timer++;
  added.push_back(i);
  for(auto[j,k]:adj[i]){
    if(j==p)
      continue;
    if(tin[j]>=0)
      stin[i]=min(stin[i],tin[j]);
    else{
      find_bridges(j,i);
      stin[i]=min(stin[i],stin[j]);
      if(stin[j]>tin[i])
        bridge[k]=true;
    }
  }
}

int type[mxN];
void find_bcc(int i,int t){
  type[i]=t;
  for(auto[j,k]:adj[i])
    if(!bridge[k]&&type[j]<0)
      find_bcc(j,t);
}

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin>>N>>M;
  FOR(i,0,M-1){
    int a,b;
    cin>>a>>b;
    adj[--a].push_back({--b,i});
    adj[b].push_back({a,i});
  }
  memset(tin,-1,sizeof(tin));
  memset(type,-1,sizeof(type));
  ll ans=0;
  FOR(r,0,N-1){
    if(tin[r]>=0)
      continue;
    added.clear();
    find_bridges(r,r);
    ans+=1ll*size(added)*(size(added)-1)*(size(added)-2);
    int B=0;
    for(int i:added)
      if(type[i]<0)
        find_bcc(i,B++);
    vt<vt<int>> bcc_adj(B),nodes(B);
    for(int i:added) {
      assert(type[i]>=0);
      nodes[type[i]].push_back(i);
      for(auto[j,k]:adj[i])
        if(bridge[k])
          bcc_adj[type[i]].push_back(type[j]);
    }
    #ifdef DEBUG
    cout<<"BCCs:\n";
    FOR(i,0,B-1){
      cout<<i<<':';
      for(int j:nodes[i])
        cout<<' '<<j+1;
      cout<<" |";
      for(int j:bcc_adj[i])
        cout<<' '<<j;
      cout<<'\n';
    }
    #endif
    vt<int> szs(B);
    function<void(int,int)> find_szs = [&](int i,int p){
      szs[i]=size(nodes[i]);
      for(int j:bcc_adj[i])
        if(j!=p){
          find_szs(j,i);
          szs[i]+=szs[j];
        }
    };
    find_szs(0,0);
    for(auto &vn:nodes){
      ll sub=0;
      for(int i:vn)
        for(auto[j,k]:adj[i])
          if(bridge[k]){
            if(szs[j]<szs[i])
              sub+=1ll*szs[j]*(szs[j]+1);
            else
              sub+=1ll*(szs[0]-szs[i])*(szs[0]-szs[i]+1);
          }
      for(int i:vn){
        ll s=sub;
        for(auto[j,k]:adj[i])
          if(bridge[k]){
            if(szs[j]<szs[i])
              s-=1ll*szs[j]*(szs[j]+1), s+=1ll*szs[j]*(szs[j]-1);
            else
              s-=1ll*(szs[0]-szs[i])*(szs[0]-szs[i]+1), s+=1ll*(szs[0]-szs[i])*(szs[0]-szs[i]-1);
          }
        #ifdef DEBUG
        cout<<"deleted from "<<i+1<<": "<<s<<'\n';
        #endif
        ans-=s;
      }
    }
  }
  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