Submission #1209079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209079		k1r1t0	Duathlon (APIO18_duathlon)	C++20	100 / 100	117 ms	47684 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 210000;

int n, m, dep[N], high[N], k, sub[N], ans;
vector<int> g[N], dt[N], dh[N], tr[N];
bool used[N];

void dfs(int v, int d = 1) {
	high[v] = dep[v] = d;
	for (int u : g[v]) {
		if (dep[u]) {
			dh[v].push_back(u);
			high[v] = min(high[v], dep[u]);
			continue;
		}
		dt[v].push_back(u);
		dfs(u, d + 1);
		high[v] = min(high[v], high[u]);
	}
}

void build(int v, int t) {
	tr[n + t].push_back(v);
	tr[v].push_back(n + t);
	for (int u : dt[v]) {
		if (high[u] < dep[v])
			build(u, t);
		else {
			k++;
			tr[n + k].push_back(v);
			tr[v].push_back(n + k);
			build(u, k);
		}
	}
}

void calc(int v, int p = -1) {
	used[v] = true;
	sub[v] = (v <= n);
	for (int u : tr[v]) if (u != p) {
		calc(u, v);
		sub[v] += sub[u];
	}
}

void solve(int v, int p = -1, int all = -1) {
	used[v] = true;
	if (all == -1)
		all = sub[v];
	for (int u : tr[v]) if (u != p)
		solve(u, v, all);
	int mul = 0, sum = 0;
	for (int u : tr[v]) {
		int cur = (u != p ? sub[u] : all - sub[v]);
		mul += sum * cur;
		sum += cur;
	}
	if (v > n)
		mul *= ((int) tr[v].size() - 2);
	ans += mul;
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
		if (!dep[i]) dfs(i);
	k = 0;
	for (int i = 1; i <= n; i++)
		if (tr[i].empty()) {
			k++;
			build(i, k);
		}
	for (int i = 1; i <= n; i++)
		if (!used[i]) calc(i);
	for (int i = 1; i <= n; i++)
		used[i] = false;
	for (int i = 1; i <= n; i++)
		if (!used[i]) solve(i);
	cout << 2 * ans;
}

• 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