제출 #1278506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278506		g4yuhg	철인 이종 경기 (APIO18_duathlon)	C++20	10 / 100	71 ms	25588 KiB

count_triplets

//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 200010
#define LOG 18
using namespace std;

const ll inf = 1e9;

bool ghuy4g;

ll n, m, par[N], num[N], low[N], timeDfs, bcc, mp[N];
vector<ll> adj[N], adj2[N], p[N], adj3[N];

ll find(ll u) {
	if (par[u] < 0) return u;
	return par[u] = find(par[u]);
}

void join(ll u, ll v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (par[u] <= par[v]) {
		par[u] += par[v];
		par[v] = u;
	}
	else {
		par[v] += par[u];
		par[u] = v;
	}
}

void dfs(ll u, ll parent) {
	num[u] = low[u] = ++ timeDfs;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		if (num[v]) {
			low[u] = min(low[u], num[v]);
			join(u, v);
		}
		else {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] == num[v]) {
				
			}
			else {
				join(u, v);
			}
		}
	}
}

ll goc[N], sz[N];
ll ans = 0;

void dfs2(ll u, ll parent) {
	sz[u] = p[u].size();
	goc[u] = goc[parent];
	for (auto v : adj2[u]) {
		if (v == parent) continue;
		dfs2(v, u);
		sz[u] += sz[v];
	}
}

ll cal(ll u, ll v) { // tinh sz[v], con cur la u
	if (sz[v] > sz[u]) {
		return sz[goc[u]] - sz[u];
	}
	return sz[v];
}

void xly(ll id) {
	ll sum = 0;
	for (auto v : adj2[id]) {
		ll xet = cal(id, v);
		//cout << " cal " << id << " " << v << " " << xet << endl;
		ans += sum * xet;
		sum += xet;
	}
	ll left = p[id].size() - 1;
	for (auto u : p[id]) {
		ans += left * (left - 1) / 2;
		ans += left * sum;
		//cout << u << " " << ans << endl;
		ll sum1 = 0;
		for (auto v : adj3[u]) {
			ll xet1 = cal(id, v);
			ans -= xet1 * sum1 * left;
			sum1 += xet1;
		}
		ans -= sum1 * left;
	}
}

void solve() {
	for (int i = 1; i <= bcc; i ++) {
		ll prevans = ans;
		xly(i);
		//cout << i << " | " << ans - prevans << endl;
	}
	cout << ans * 2 << endl;
}

void pre() {
	for (int i = 1; i <= n; i ++) {
		if (num[i] == 0) dfs(i, i);
	}
	for (int i = 1; i <= n; i ++) {
		ll r = find(i);
		if (mp[r] == 0) {
			mp[r] = ++ bcc;
		}
		mp[i] = mp[r];
		p[mp[i]].push_back(i);
	}
	//cout << "bcc " << bcc << endl;
	for (int id = 1; id <= bcc; id ++) {
		for (auto it : p[id]) {
			//cout << it << " ";
		}
		//cout << endl;
	}
	for (int i = 1; i <= bcc; i ++) {
		for (auto u : p[i]) {
			for (auto v : adj[u]) {
				if (mp[u] == mp[v]) continue;
				adj2[mp[u]].push_back(mp[v]);
				//adj2[mp[v]].push_back(mp[u]);
				//cout << mp[u] << " <-> " << mp[v] << endl;
				adj3[u].push_back(mp[v]);
				//adj3[v].push_back(mp[u]);
			}
		}
	}
	for (int i = 1; i <= bcc; i ++) {
		if (goc[i] == 0) {
			goc[i] = i;
			dfs2(i, i);
		}
	}
}

bool klinh;

signed main() {
	memset(par, -1, sizeof(par));
	//freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		ll u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	pre();
	solve();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	return 0;
}

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