Submission #265287

#	Time	Username	Problem	Language	Result	Execution time	Memory
265287		extraterrestrial	Duathlon (APIO18_duathlon)	C++14	36 / 100	493 ms	16816 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], have_cycle;
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];
    }
    else if (u != pr[v]) {
      have_cycle = true;
    }
  }
}

int sum = 0;
vector<int> path;
bool was[11][11][11];
void go(int mask) {
  int cnt = __builtin_popcount(mask);
  if (cnt >= 3) {
    for (int i = 1; i + 1 < SZ(path); i++) {
      if (!was[path[0]][path[i]][path.back()]) {
        was[path[0]][path[i]][path.back()] = true;
        sum++;
      }
    }
  }
  for (auto u : g[path.back()]) {
    if ((mask >> u) & 1) {
      continue;
    }
    path.pb(u);
    go(mask | (1 << u));
    path.pop_back();
  }
}

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 == 2 * sz[i]) {
          ans += 1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2);
        }
        else {
          assert(sum_sz == 2 * (sz[i] - 1));
          ans += 1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2) / 3;
        }
      }
    }
    cout << ans << '\n';
    exit(0);
  }
  if (n <= 10) {
    for (int i = 1; i <= n; i++) {
      path.pb(i);
      go(1 << i);
      path.pop_back();
      //cout << sum << '\n';
    }
    cout << sum << '\n';
    exit(0);
  }
  for (int i = 1; i <= n; i++) {
    if (!used[i]) {
      dfs(i, i);
    }
  }
  if (!have_cycle) {
    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';
  }
  else {
    assert(false);
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 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