Submission #265129

#	Time	Username	Problem	Language	Result	Execution time	Memory
265129		extraterrestrial	Duathlon (APIO18_duathlon)	C++14	23 / 100	89 ms	15068 KiB

count_triplets

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back  
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll    

const int N = 1e5 + 10;
vector<int> g[N], comp;
bool used[N];
int sz[N], root[N], pr[N];

void dfs(int v, int rt) {
  comp.pb(v);
  used[v] = true;
  sz[v] = 1;
  root[v] = rt;
  for (auto u : g[v]) {
    if (!used[u]) {
      pr[u] = v;
      dfs(u, rt);
      sz[v] += sz[u];
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  bool gr2 = true;
  for (int i = 1; i <= n; i++) {
    if (SZ(g[i]) > 2) {
      gr2 = false;
      break;
    }
  }
  if (gr2) {
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
      if (!used[i]) {
        comp = {};
        dfs(i, i);
        int sum_sz = 0;
        for (int v : comp) {
          sum_sz += SZ(g[v]);
        } 
        if (sum_sz % 4 == 0) {
          ans += 1ll * n * (n - 1) * (n - 2);
        }
        else {
          ans += 1ll * n * (n - 1) * (n - 2) / 3;
        }
      }
    }
    cout << ans << '\n';
    exit(0);
  }
  for (int i = 1; i <= n; i++) {
    if (!used[i]) {
      dfs(i, i);
    }
  }
  ll ans = 0;
  for (int v = 1; v <= n; v++) {
    for (auto u : g[v]) {
      if (u == pr[v]) {
        ans += (sz[root[v]] - sz[v]) * 1ll * (sz[v] - 1);
      }
      else {
        ans += sz[u] * 1ll * (sz[root[v]] - sz[u] - 1);
      }
    }
  }
  cout << ans << '\n';
}

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