Submission #658742

#	Time	Username	Problem	Language	Result	Execution time	Memory
658742		600Mihnea	Duathlon (APIO18_duathlon)	C++17	100 / 100	217 ms	46288 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 300000 + 7;
int n;
int m;
vector<int> g[N];
vector<int> g2[N];
int dep[N];
int mindep[N];
vector<vector<int>> all;
vector<pair<int, int>> stk;
int dim;
int inside[N];

void dfs(int a) {
  mindep[a] = dep[a];

  for (auto &b : g[a]) {
    if (dep[b] == -1) {
      dep[b] = 1 + dep[a];
      stk.push_back({a, b});
      dfs(b);
      mindep[a] = min(mindep[a], mindep[b]);
      if (mindep[b] >= dep[a]) {

        vector<int> cur;
        while (1) {
          assert(!stk.empty());
          auto it = stk.back();
          cur.push_back(it.first);
          cur.push_back(it.second);
          stk.pop_back();
          if (it == make_pair(a, b)) {
            break;
          }
        }
        sort(cur.begin(), cur.end());
        cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
        all.push_back(cur);

        dim++;
        for (auto &v : cur) {
          inside[dim]++;
          g2[v].push_back(dim);
          g2[dim].push_back(v);
        }
      }
    } else {
      if (dep[b] < dep[a] - 1) {
        mindep[a] = min(mindep[a], dep[b]);
      }
    }
  }
}

int sub[N];
int ninit;
int total;

ll sol = 0;

void solve(int a) {
  sub[a] = (a <= ninit);
  vector<int> kids;
  for (auto &b : g[a]) {
    if (sub[b] == -1) {
      solve(b);
      sub[a] += sub[b];
      kids.push_back(b);
    }
  }
  g[a] = kids;
}

int rt;

void solve2(int a, int pr = -1) {
  for (auto &b : g[a]) {
    solve2(b, a);
    if (a > ninit) {
      sol -= 1LL * (inside[a] - 1) * (sub[b]) * (sub[b] - 1);
    }
  }
  if (a > ninit) {
    sol -= 1LL * (inside[a] - 1) * (total - sub[a]) * (total - sub[a] - 1);
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

///  freopen ("input.txt", "r", stdin);

  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
    sub[a] = -1;
  }
  for (int i = 1; i <= n; i++) {
    dep[i] = -1;
  }
  ninit = n;
  dim = n;
  for (int i = 1; i <= n; i++) {
    if (dep[i] == -1) {
      dep[i] = 0;
      dfs(i);
      assert(stk.empty());
    }
  }

  n = dim;
  for (int i = 1; i <= n; i++) {
    g[i] = g2[i];
    sub[i] = -1;
  }

  for (int i = 1; i <= n; i++) {
    if (sub[i] == -1) {
      solve(i);
      total = sub[i];
      sol += 1LL * (total) * (total - 1) * (total - 2);
      ///cout << "sol = " << sol << "\n";
      solve2(i);
      //cout << " ----------------------- \n";
    }
  }
  cout << sol << "\n";
  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