Submission #405537

#	Time	Username	Problem	Language	Result	Execution time	Memory
405537		BERNARB01	Duathlon (APIO18_duathlon)	C++17	31 / 100	211 ms	29048 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class graph {
  public:
  struct edge {
    int from;
    int to;
    T cost;
  };

  vector<edge> edges;
  vector< vector<int> > g;
  int n;

  function<bool(int)> ignore;

  graph(int _n) : n(_n) {
    g.resize(n);
    ignore = nullptr;
  }

  virtual int add(int from, int to, T cost) = 0;

  virtual void set_ignore_edge_rule(const function<bool(int)> &f) {
    ignore = f;
  }

  virtual void reset_ignore_edge_rule() {
    ignore = nullptr;
  }
};

template <typename T>
class undigraph : public graph<T> {
  public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;

  undigraph(int _n) : graph<T>(_n) {
  }

  int add(int from, int to, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int) edges.size();
    g[from].push_back(id);
    g[to].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }
};

template <typename T>
class dfs_undigraph : public undigraph<T> {
  public:
  using undigraph<T>::edges;
  using undigraph<T>::g;
  using undigraph<T>::n;
  using undigraph<T>::ignore;

  vector<int> pv;
  vector<int> pe;
  vector<int> order;
  vector<int> pos;
  vector<int> end;
  vector<int> sz;
  vector<int> root;
  vector<int> depth;
  vector<int> min_depth;
  vector<T> dist;
  vector<int> was;
  int attempt;

  dfs_undigraph(int _n) : undigraph<T>(_n) {
  }

  void init() {
    pv = vector<int>(n, -1);
    pe = vector<int>(n, -1);
    order.clear();
    pos = vector<int>(n, -1);
    end = vector<int>(n, -1);
    sz = vector<int>(n, 0);
    root = vector<int>(n, -1);
    depth = vector<int>(n, -1);
    min_depth = vector<int>(n, -1);
    dist = vector<T>(n);
    was = vector<int>(n, -1);
    attempt = 0;
  }

  void clear() {
    pv.clear();
    pe.clear();
    order.clear();
    pos.clear();
    end.clear();
    sz.clear();
    root.clear();
    depth.clear();
    min_depth.clear();
    dist.clear();
    was.clear();
  }

  private:
  void do_dfs(int v) {
    was[v] = attempt;
    pos[v] = (int) order.size();
    order.push_back(v);
    sz[v] = 1;
    min_depth[v] = depth[v];
    for (int id : g[v]) {
      if (id == pe[v] || (ignore != nullptr && ignore(id))) {
        continue;
      }
      auto &e = edges[id];
      int to = e.from ^ e.to ^ v;
      if (was[to] == attempt) {
        min_depth[v] = min(min_depth[v], depth[to]);
        continue;
      }
      depth[to] = depth[v] + 1;
      dist[to] = dist[v] + e.cost;
      pv[to] = v;
      pe[to] = id;
      root[to] = (root[v] != -1 ? root[v] : to);
      do_dfs(to);
      sz[v] += sz[to];
      min_depth[v] = min(min_depth[v], min_depth[to]);
    }
    end[v] = (int) order.size() - 1;
  }

  void do_dfs_from(int v) {
    ++attempt;
    depth[v] = 0;
    dist[v] = T{};
    root[v] = v;
    pv[v] = pe[v] = -1;
    do_dfs(v);
  }

  public:
  void dfs(int v, bool clear_order = true) {
    if (pv.empty()) {
      init();
    } else {
      if (clear_order) {
        order.clear();
      }
    }
    do_dfs_from(v);
  }

  void dfs_all() {
    init();
    for (int v = 0; v < n; v++) {
      if (depth[v] == -1) {
        do_dfs_from(v);
      }
    }
    assert((int) order.size() == n);
  }
};

template <typename T>
vector<int> find_bicone(dfs_undigraph<T> &g, int &cnt) {
  g.dfs_all();
  vector<int> vertex_comp(g.n);
  cnt = 0;
  for (int i : g.order) {
    if (g.pv[i] == -1 || g.min_depth[i] == g.depth[i]) {
      vertex_comp[i] = cnt++;
    } else {
      vertex_comp[i] = vertex_comp[g.pv[i]];
    }
  }
  return vertex_comp;
}

struct dsu {
	int nCC;
	vector<int> pr, sz, rank;
	dsu(int n) {
		nCC = n;
		pr.resize(n);
		sz.assign(n, 1);
		rank.assign(n, 1);
		iota(pr.begin(), pr.end(), 0);
	}
	int fnd(int u) {
		if (u == pr[u]) {
			return u;
		}
		pr[u] = fnd(pr[u]);
		return pr[u];
	}
	bool unate(int u, int v) {
		u = fnd(u); v = fnd(v);
		if (u == v) {
			return false;
		}
		--nCC;
		if (rank[u] > rank[v]) {
			swap(u, v);
		}
		pr[u] = v;
		rank[v] += (rank[u] == rank[v]);
		sz[v] += sz[u];
		return true;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	dfs_undigraph<int> gg(n);
	dsu se(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		--u; --v;
		gg.add(u, v);
		se.unate(u, v);
	}
	int cnt;
	vector<int> comp = find_bicone(gg, cnt);
	vector<int> a(cnt, 0);
	vector<int> dsu_par(cnt);
	for (int i = 0; i < n; i++) {
		a[comp[i]]++;
		dsu_par[comp[i]] = i;
	}
	dsu se2(n);
	for (int i = 0; i < n; i++) {
		se2.unate(i, dsu_par[comp[i]]);
	}
	vector<vector<int>> g(cnt);
	vector<int> deg(cnt, 0);
	for (auto e : gg.edges) {
		if (se2.unate(e.from, e.to)) {
			g[comp[e.from]].push_back(comp[e.to]);
			g[comp[e.to]].push_back(comp[e.from]);
			deg[comp[e.from]]++;
			deg[comp[e.to]]++;
		}
	}
	long long ans = 0;
	for (int i = 0; i < cnt; i++) {
		dsu_par[i] = se.fnd(dsu_par[i]);
		if (a[i] > 2) {
			ans += a[i] * 1LL * (a[i] - 1) * (a[i] - 2);
		}
		if (a[i] > 1) {
			ans += (a[i] - deg[i]) * 2LL * (a[i] - 1) * (se.sz[dsu_par[i]] - a[i]);
		}
	}
	vector<long long> sbt(cnt, 0);
	function<int(int, int)> dfs0 = [&](int u, int p) {
		int r = 1;
		sbt[u] = a[u];
		for (int v : g[u]) {
			if (v != p) {
				r += dfs0(v, u);
				sbt[u] += sbt[v];
			}
		}
		return r;
	};
	function<void(int, int, int)> DFS = [&](int u, int p, int nn) {
		for (int v : g[u]) {
			if (v != p) {
				DFS(v, u, nn);
			}
		}
		long long sum = nn - 1;
		long long sbtp = nn - sbt[u];
		ans += sbtp * 1LL * (sum - sbtp);
		for (int v : g[u]) {
			if (v != p) {
				ans += sbt[v] * 1LL * (sum - sbt[v]);
			}
		}
	};
	for (int i = 0; i < cnt; i++) {
		if (sbt[i] == 0) {
			int sz = dfs0(i, -1);
			if (sz > 2) {
				DFS(i, -1, sz);
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 0 / 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