Submission #1209070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209070		k1r1t0	Duathlon (APIO18_duathlon)	C++20	0 / 100	148 ms	47496 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];

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 = 1) {
	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 solve(int v, int p = -1) {
	sub[v] = (v <= n);
	for (int u : tr[v]) if (u != p) {
		solve(u, v);
		sub[v] += sub[u];
	}
	int mul = 0, sum = 0;
	for (int u : tr[v]) {
		int cur = (u != p ? sub[u] : n - 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;
	if (n < 3) {
		cout << 0;
		return 0;
	}
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	k = 1;
	dfs(1);
	build(1);
	solve(1);
	cout << 2 * ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10