제출 #975420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975420		dubabuba	Duathlon (APIO18_duathlon)	C++14	0 / 100	119 ms	53244 KiB

count_triplets

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

typedef long long i64;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

template<typename T> pair<T, T> SP(T L, T R) { return MP(min(L, R), max(L, R)); }
template<typename T> void ono_min(T &MIN, T CMP) { if(MIN > CMP) MIN = CMP; }
template<typename T> void ono_max(T &MAX, T CMP) { if(MAX < CMP) MAX = CMP; }
const int mxn = 2e5 + 10;

vector<int> adj[mxn];
vector<pii> edges;

int vis[mxn], low[mxn];
int n, m, TIME;

void dfs(int u, int p) {
	TIME++;
	vis[u] = TIME;
	low[u] = TIME;
	for(int v : adj[u]) {
		if(v == p) continue;
		if(vis[v] == 0) dfs(v, u);
		ono_min(low[u], low[v]);
	}
}

vector<int> cyc_node;
vector<int> cyc_edge[mxn];
int col[mxn], cnt[mxn];

int colour(int u) {
	if(col[u] < 0) return u;
	return col[u] = colour(col[u]);
}

bool unite(int u, int v) {
	u = colour(u);
	v = colour(v);
	if(u == v) return 0;

	if(col[u] > col[v]) swap(u, v);
	col[u] += col[v];
	col[v] = u;
	return 1;
}

void build() {
	for(int i = 1; i <= n; i++) {
		if(vis[i] == 0)
			dfs(i, i);
	}

	for(int i = 1; i <= n; i++) {
		col[low[i]]--;
		cnt[low[i]]++;
		if(low[i] == i)
			cyc_node.push_back(i);
	}

	set<pii> s;
	for(pii p : edges) {
		int u = low[p.ff];
		int v = low[p.ss];
		if(u == v) continue;
		s.insert(SP(u, v));
		unite(u, v);
	}

	for(pii p : s) {
		int u = p.ff;
		int v = p.ss;
		cyc_edge[u].push_back(v);
		cyc_edge[v].push_back(u);
	}

	// assert(cyc_node.size() == n);
}

int chi[mxn];
i64 kv_sum[mxn];
i64 sum_kv[mxn];
i64 ans = 0;

void dfs_solve(int u, int p) {
	vis[u] = 1;
	for(int v : cyc_edge[u]) {
		if(p == v) continue;
		if(vis[v]) continue;
		dfs_solve(v, u);

		chi[u] += chi[v];
		kv_sum[u] += 1LL * chi[u] * chi[u];
		sum_kv[u] += chi[v];

		ans += 1LL * (cnt[u] - 1) * cnt[v] * 2;
		if(cnt[u] > 2)
		ans += 1LL * (cnt[u] - 2) * (cnt[u] - 3) * cnt[v] * 2;
		// cout << u << "+ " << (cnt[u] - 1) * cnt[v] * 2 << endl;
	}

	sum_kv[u] = sum_kv[u] * sum_kv[u];
	assert(cnt[u] == 1);
	chi[u] += cnt[u];

	i64 t = sum_kv[u] - kv_sum[u];
	ans += t;

	i64 total = -col[colour(u)];
	i64 UP = total - chi[u];
	i64 DO = chi[u] - cnt[u];
	ans += UP * DO * 2;

	ans += UP * (cnt[u] - 1) * 2;
	ans += UP * (cnt[u] - 1) * (cnt[u] - 2) * 2;

	// cout << u << "+ " << t << endl;
	// cout << u << "+ " << UP * DO * 2 << endl;
	// cout << u << "+ " << UP * (cnt[u] - 1) * 2 << endl;
	// cout << u << "+ " << UP * (cnt[u] - 1) * (cnt[u] - 2) * 2 << endl;
}

i64 nc(i64 a) {
	return a * (a - 1) * (a - 2);
}

void solve() {
	memset(vis, 0, sizeof vis);
	for(int u : cyc_node) {
		if(vis[u] == 0)
			dfs_solve(u, u);
		ans += nc(cnt[u]);
	}
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.push_back(SP(u, v));
	}

	build();
	solve();

	cout << ans << endl;
	return 0;
}

• 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