Submission #850867

#	Time	Username	Problem	Language	Result	Execution time	Memory
850867		qthang2k11	Duathlon (APIO18_duathlon)	C++17	100 / 100	68 ms	26936 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e5 + 5;

vector<int> adj[N];
int n, m;
ll ans = 0;

int num[N], low[N], tcur = 0, sz[N * 2];
vector<int> adj2[N * 2];

int cnt = 0, bi_cnt = 0;
stack<int> st;

void dfs_init(int x, int p) {
	++cnt;
	st.emplace(x);
	num[x] = low[x] = ++tcur;
	for (int y: adj[x]) {
		if (y == p) continue;
		if (num[y]) {
			low[x] = min(low[x], num[y]);
		} else {
			dfs_init(y, x);
			low[x] = min(low[x], low[y]);
			if (low[y] >= num[x]) {
				bi_cnt++;
				adj2[x].emplace_back(n + bi_cnt);
				auto &bi = adj2[n + bi_cnt];
				while (bi.empty() || bi.back() != y) {
					bi.emplace_back(st.top());
					st.pop();
				}
			}
		}
	}
}

// (S->C->F)
void dfs(int x) {
	sz[x] = (x <= n);
	for (int y: adj2[x]) {
		dfs(y);
		sz[x] += sz[y];
		if (x > n) {
			// choose one of (bi-comp[x] except y) as a C, choose the remaining two from child[y]
			ans -= 1LL * adj2[x].size() * sz[y] * (sz[y] - 1);
		}
	}
	if (x > n) {
		ans -= 1LL * adj2[x].size() * (cnt - sz[x]) * (cnt - sz[x] - 1);
	}
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		adj[x].emplace_back(y);
		adj[y].emplace_back(x);
	}
	for (int i = 1; i <= n; i++) {
		if (num[i]) continue;
		cnt = 0;
		dfs_init(i, 0);
		ans += 1LL * cnt * (cnt - 1) * (cnt - 2);
		dfs(i);
	}
	cout << ans;
	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