Submission #702137

#	Time	Username	Problem	Language	Result	Execution time	Memory
702137		Abrar_Al_Samit	Duathlon (APIO18_duathlon)	C++17	100 / 100	173 ms	39244 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;


const int nax = 1e5 + 2;
vector<int>tree[nax * 2];
int n, m;
int sub[nax * 2];
long long ans = 0;

void ad(int u, int v) {
  tree[u].push_back(v);
  tree[v].push_back(u);
}
template<int SZ> struct BCC {
  vector<int>adj[SZ];
  int N;
  int pre_order[SZ], low[SZ], comp[SZ], par[SZ];
  int compsz[SZ];
  int ti = 0;

  vector<pair<int,int>>st;
  vector<vector<pair<int,int>>>fin;

  void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  void BCCutil(int u, bool root = 0) {
    pre_order[u] = low[u] = ti++;
    int child = 0;

    for(int i : adj[u]) if(i!=par[u]) {
      //cerr<<u<<' '<<i<<'\n';
      if(pre_order[i]==-1) {
        ++child, par[i] = u;
        st.emplace_back(u, i);
        BCCutil(i);
        low[u] = min(low[u], low[i]);

        if((root && child>1) || (!root && low[i]>=pre_order[u])) { // cut vertex
          //cerr<<u<<'\n';
          vector<pair<int,int>>temp;
          while(st.back()!=make_pair(u, i)) {
            temp.push_back(st.back());
            st.pop_back();
          }
          temp.push_back(st.back()), st.pop_back();
          fin.push_back(temp);
        }

      } else if(pre_order[i] < pre_order[u]) {
        low[u] = min(low[u], pre_order[i]);
        st.emplace_back(u, i);
      }
    }
  }

  void bcc() {
    for(int i=1; i<=N; ++i) {
      pre_order[i] = par[i] = low[i] = -1;
    }
    for(int i=1; i<=N; ++i) {
      if(pre_order[i]==-1) {
        BCCutil(i, 1);
        if(!st.empty()) fin.push_back(st);
        st.clear();
      }
    }


    int co = 0;
    for(auto a : fin) {
      set<int>s;
      for(auto b : a) {
        s.insert(b.first), s.insert(b.second);
      }
      ++co;
      compsz[co] = s.size();
      for(int i : s) ad(i, co+N);
    }
  }
};
BCC<nax>a;

int dfs1(int v, int p) {
  sub[v] = v<=n ? 1 : 0;
  for(int u : tree[v]) if(u!=p) {
    sub[v] += dfs1(u, v);
  }
  return sub[v];
}
void dfs2(int v, int r, int prv) {
  if(v<=n) {
    for(int u : tree[v]) {
      if(u==prv) {
        ans -= 1LL * sub[v] * (sub[v] - 1) * (a.compsz[u-a.N]-1);
      } else {
        ans -= 1LL * (a.compsz[u-a.N]-1) * (sub[r]-sub[u]) * (sub[r]-sub[u]-1);
      }
    }
  }

  for(int u : tree[v]) if(u!=prv) {
    dfs2(u, r, v);
  }
}
void PlayGround() {
  cin>>n>>m;
  a.N = n;

  for(int i=0; i<m; ++i) {
    int u, v;
    cin>>u>>v;
    a.addEdge(u, v);
  }

  a.bcc();

  memset(sub, -1, sizeof sub);
  for(int i=1; i<=n; ++i) if(sub[i]==-1) {
    dfs1(i, i);
    ans += 1LL * sub[i] * (sub[i]-1) * (sub[i]-2);

    dfs2(i, i, i);
  }
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

• 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