제출 #603334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
603334		GusterGoose27	Duathlon (APIO18_duathlon)	C++11	0 / 100	276 ms	40504 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
const int MAXM = 2e5;
const int treeMAXN = 2e5; // n bccs, n cut nodes

typedef long long ll;

vector<int> tree_edges[treeMAXN];
vector<int> edges[MAXN];
int n, m;
vector<int> cut_verts;
bool is_cut[MAXN];
int depth[MAXN];
int lp[MAXN];
vector<int> bccs_in[MAXN];
int bcc_sz[treeMAXN];
int t = 0;
bool vis[treeMAXN];
ll ans = 0;
int rt;
vector<int> cent_graph[treeMAXN];
int sz[treeMAXN];
vector<int> in_decomp;
vector<int> in_stree[treeMAXN];
ll smult[treeMAXN];
ll psum[treeMAXN];

void print(vector<int> &v) {
	for (int i: v) {
		cout << i << " ";
	}
	cout << endl;
}

void find_cut(int i, int p = -1) {
	lp[i] = depth[i];
	int c = 0;
	bool is_point = 0;
	for (int next: edges[i]) {
		if (next == p) continue;
		if (depth[next] != -1) {
			lp[i] = min(lp[i], depth[next]);
			continue;
		}
		c++;
		depth[next] = 1+depth[i];
		find_cut(next, i);
		lp[i] = min(lp[i], lp[next]);
		if (lp[next] >= depth[i]) is_point = 1;
	}
	if (i == 0) {
		if (c > 1) {
			cut_verts.push_back(i);
			is_cut[i] = 1;
		}
	}
	else if (is_point) {
		cut_verts.push_back(i);
		is_cut[i] = 1;
	}
}

void make_bcc(int s) {
	vis[s] = 1;
	bcc_sz[t]++;
	for (int next: edges[s]) {
		if (vis[next]) continue;
		if (is_cut[next]) {
			bccs_in[next].push_back(t);
			continue;
		}
		make_bcc(next);
	}
}

void make_sz(int cur, int p = -1) {
	sz[cur] = 1;
	for (int next: tree_edges[cur]) {
		if (vis[next] || next == p) continue;
		make_sz(next, cur);
		sz[cur] += sz[next];
	}
}

int make_decomp(int cur) {
	make_sz(cur);
	int tot = sz[cur];
	bool f = 1;
	int p = -1;
	while (f) {
		f = 0;
		for (int next: tree_edges[cur]) {
			if (vis[next] || next == p) continue;
			if (sz[next] > tot/2) {
				p = cur;
				cur = next;
				f = 1;
				break;
			}
		}
	}
	vis[cur] = 1;
	for (int next: tree_edges[cur]) {
		if (!vis[next]) cent_graph[cur].push_back(make_decomp(next));
	}
	return cur;
}

void dfs(int cur, int p, ll rtsum, int stree) {
	rtsum += bcc_sz[cur];
	ll cval = bcc_sz[cur];
	smult[cur] = cval*rtsum;
	psum[cur] = cval;
	in_decomp.push_back(cur);
	in_stree[stree].push_back(cur);
	for (int next: tree_edges[cur]) {
		if (vis[next] || next == p) continue;
		dfs(next, cur, rtsum, stree);
	}
}

void make_ans(int cur) {
	vis[cur] = 1;
	in_decomp.clear();
	in_decomp.push_back(cur);
	ll rtval = bcc_sz[cur];
	smult[cur] = rtval*rtval;
	psum[cur] = rtval;
	for (int next: tree_edges[cur]) {
		if (vis[next]) continue;
		dfs(next, cur, rtval, next);
		//cout << next << endl;
		//print(in_stree[next]);
	}
	//print(in_decomp);
	ll s = 0;
	ll p = 0;
	ll q = 0;
	for (int v: in_decomp) {
		s += smult[v];
		p += psum[v];
		q += psum[v]*psum[v];
	}
	//cout << s << ' ' << p << ' ' << q << endl;
	ll add = 2*s*p-p*p*rtval-2*p*q+rtval*rtval*rtval;
	for (int next: tree_edges[cur]) {
		if (vis[next]) continue;
		s = 0;
		p = 0;
		q = 0;
		for (int v: in_stree[next]) {
			s += smult[v];
			p += psum[v];
			q += psum[v]*psum[v];
		}
		add -= 2*s*p-p*p*rtval-2*p*q;
	}
	//cout << add << endl << endl;
	ans += add;
	for (int next: cent_graph[cur]) make_ans(next);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y; x--; y--;
		edges[x].push_back(y);
		edges[y].push_back(x);
	}
	fill(depth, depth+n, -1);
	depth[0] = 0;
	find_cut(0);
	for (int i = 0; i < n; i++) {
		if (is_cut[i] || vis[i]) continue;
		make_bcc(i); t++;
	}
	assert(t+cut_verts.size() <= treeMAXN);
	map<int, int> pos_of;
	int d = 0;
	for (int v: cut_verts) {
		pos_of[v] = d;
		d++;
	}
	for (int v: cut_verts) {
		for (int next: edges[v]) {
			if (is_cut[next]) tree_edges[pos_of[v]+t].push_back(pos_of[next]+t);
		}
		for (int next: bccs_in[v]) {
			tree_edges[pos_of[v]+t].push_back(next);
			tree_edges[next].push_back(pos_of[v]+t);
		}
		bcc_sz[pos_of[v]+t] = 1;
	}
	n = t+cut_verts.size();
	//for (int i = 0; i < n; i++) print(tree_edges[i]);
	fill(vis, vis+n, 0);
	rt = make_decomp(0);
	fill(vis, vis+n, 0);
	make_ans(rt);
	ll p2sum = 0;
	ll over_sum = 0;
	ll ex = 0;
	for (int i = 0; i < n; i++) {
		ll cur = bcc_sz[i];
		p2sum += cur*(cur-1);
		over_sum += cur;
		ex += 2*cur*(cur-1);
	}
	ans += p2sum*over_sum-ex;
	cout << ans << "\n";
}

• 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