제출 #158233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158233		maruii	철인 이종 경기 (APIO18_duathlon)	C++14	49 / 100	1142 ms	1048576 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define ff first
#define ss second

int n, N, M, dfn[100005], dfnn, low[100005], cpnn, sz[100005], Gn;
vector<int> edge[100005], bdge[200005];
ll ans;
bool vis[100005];

void dfs(int x, int p) {
	dfn[x] = low[x] = ++dfnn;
	N++;
	for (auto i : edge[x]) {
		if (i == p) continue;
		if (dfn[i]) {
			if (dfn[i] < dfn[x]) low[x] = min(low[x], dfn[i]);
			continue;
		}
		dfs(i, x);
		low[x] = min(low[x], low[i]);
	}
}

void bcc(int x, int c) {
	vis[x] = 1;
	if (c) {
		bdge[c].push_back(x);
		bdge[x].push_back(c);
	}
	for (auto i : edge[x]) {
		if (vis[i]) continue;
		if (low[i] >= dfn[x]) {
			++cpnn;
			bdge[x].push_back(cpnn);
			bdge[cpnn].push_back(x);
			bcc(i, cpnn);
		}
		else bcc(i, c);
	}
}

void calc(int x, int p) {
	sz[x] = x <= n;
	for (auto i : bdge[x]) {
		if (i == p) continue;
		calc(i, x);
		sz[x] += sz[i];
	}
	if (x > n) for (auto i : bdge[x]) {
		if (i == p) ans -= 1ll * (bdge[x].size() - 1) * (N - sz[x]) * (N - sz[x] - 1);
		else ans -= 1ll * (bdge[x].size() - 1) * sz[i] * (sz[i] - 1);
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> M;
	for (int i = 0; i < M; ++i) {
		int x, y; cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	cpnn = n;
	for (int i = 1; i <= n; ++i) {
		if (dfn[i]) continue;
		N = 0;
		dfs(i, 0);
		ans += 1ll * N * (N - 1) * (N - 2);
		bcc(i, 0);
		calc(i, 0);
	}
	cout << ans;
	return 0;
}

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