Submission #49842

#	Time	Username	Problem	Language	Result	Execution time	Memory
49842		zemen	Duathlon (APIO18_duathlon)	C++17	100 / 100	505 ms	62428 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define int ll

const int maxn = 500100;
vector<int> g[maxn];
bool used[maxn];
int up[maxn];
int in[maxn];
int timer = 0;

bool cp[maxn];
int vid[maxn];
vector<vector<pair<int, int>>> comp;

int w[maxn];
vector<int> t[maxn];

vector<pair<int, int>> st;
void dfs(int u, int prev = -1) {
  in[u] = up[u] = timer++;
  used[u] = true;
  int nbad = prev != -1;
  for (int v : g[u]) {
    if (v == prev) {
      continue;
    }
    if (used[v] && in[v] >= in[u]) {
      continue;
    }
    auto ce = pair<int, int>(u, v);
    st.push_back(ce);
    if (!used[v]) {
      dfs(v, u);
      up[u] = min(up[u], up[v]);
      if (up[v] >= in[u]) {
        comp.emplace_back();
        ++nbad;
        while (true) {
          auto e = st.back();
          st.pop_back();
          comp.back().push_back(e);
          if (e == ce) {
            break;
          }
        }
      }
    } else {
      up[u] = min(up[u], in[v]);
    }
  }
  cp[u] = nbad >= 2;
}

ll ss[maxn];
ll cnt[maxn];
ll ts[maxn];
void pre(int u, int s, int prev = -1) {
  ts[u] = s;
  in[u] = timer++;
  cnt[u] = w[u];
  ss[u] = ll(s - 1) * (s - 2);
  for (int v : t[u]) {
    if (v == prev) {
      continue;
    }
    pre(v, s, u);
    cnt[u] += cnt[v];
    ss[u] -= cnt[v] * (cnt[v] - 1);
  }
  ll cntup = s - cnt[u];
  ss[u] -= cntup * (cntup - 1);
}

int tsize(int u, int prev = -1) {
  used[u] = true;
  int res = w[u];
  for (int v : t[u]) {
    if (v == prev) {
      continue;
    }
    res += tsize(v, u);
  }
  return res;
}

signed main() {
#ifdef LOCAL
  assert(freopen("c.in", "r", stdin));
#endif
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 0; i < n; ++i) {
    if (!used[i]) {
      dfs(i);
      assert(st.empty());
    }
  }

  //for (int i = 0; i < n; ++i) {
    //cerr << cp[i] << ' ';
  //}
  //cerr << '\n';
  //for (auto v : comp) {
    //for (auto e : v) {
      //cerr << "(" << e.first << " " << e.second << ") ";
    //}
    //cerr << '\n';
  //}

  for (int i = 0; i < (int) comp.size(); ++i) {
    set<int> vs;
    for (auto e : comp[i]) {
      for (int u : {e.first, e.second}) {
        if (!cp[u]) {
          vs.insert(u);
        }
      }
    }
    w[i] = (int) vs.size();
    for (int u : vs) {
      vid[u] = i;
    }
  }
  int N = (int) comp.size();
  for (int i = 0; i < n; ++i) {
    if (cp[i]) {
      w[N] = 1;
      vid[i] = N++;
    }
  }
  for (int i = 0; i < (int) comp.size(); ++i) {
    for (auto e : comp[i]) {
      int u, v;
      tie(u, v) = e;
      if (vid[u] == vid[v]) {
        continue;
      }
      if (!cp[u]) {
        swap(u, v);
      }
      assert(cp[u]);
      if (cp[v]) {
        u = vid[u], v = vid[v];
        t[u].push_back(i);
        t[v].push_back(i);
        t[i].push_back(u);
        t[i].push_back(v);
        continue;
      }
      u = vid[u], v = vid[v];
      t[u].push_back(i);
      t[i].push_back(u);
    }
  }
  for (int i = 0; i < N; ++i) {
    sort(t[i].begin(), t[i].end());
    t[i].erase(unique(t[i].begin(), t[i].end()), t[i].end());
    //cerr << w[i] << ": ";
    //for (int v : t[i]) {
      //cerr << v+1 << ' ';
    //}
    //cerr << '\n';
  }
  
  memset(used, 0, sizeof(used));
  timer = 0;
  for (int i = 0; i < N; ++i) {
    if (used[i]) {
      continue;
    }
    int s = tsize(i);
    pre(i, s);
  }
  ll ans = 0;
  for (int i = 0; i < N; ++i) {
    ll cur = ss[i] * w[i];
    ans += cur;
    //cerr << "cur: " << i+1 << ' ' << cur << '\n';
    //cerr << "ts " << ss[i] << '\n';
    if (i < (int) comp.size()) {
      continue;
    }
    for (auto v : t[i]) {
      ll cntc;
      if (in[v] < in[i]) {
        cntc = cnt[i];
      } else {
        cntc = ts[i] - cnt[v];
      }
      ll fix = ss[v];
      fix += cntc * (cntc - 1);
      fix -= (ts[i] - 1) * (ts[i] - 2);
      ll ns = ts[i] - cntc;
      fix += ns * (ns - 1);
      //cerr << "fix: " << i+1 << ' ' << v+1 << ' ' << cntc << ' ' << ns << ' ' << fix << '\n';
      ans += fix;
    }
  }
  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