oj.uz

Submission #603349

# Submission time Handle Problem Language Result Execution time Memory
603349 2022-07-24T04:00:59 Z GusterGoose27 Duathlon (APIO18_duathlon) C++11
0 / 100
 639 ms 1048576 KB 
#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];
unordered_set<int> bccs_in[MAXN];
int bcc_sz[treeMAXN];
int t = 0;
bool vis[treeMAXN];
ll ans = 0;
vector<int> rts;
vector<vector<int>> comps;
vector<int> cent_graph[treeMAXN];
int sz[treeMAXN];
vector<int> in_decomp;
vector<int> in_stree[treeMAXN];
ll smult[treeMAXN];
ll psum[treeMAXN];
bool flag = 0;

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

void print(unordered_set<int> &v) {
	if (!flag) return;
	for (int i: v) {
		cout << i << " ";
	}
	cout << endl << endl;
}

void find_cut(int i, int s, 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, s, i);
		lp[i] = min(lp[i], lp[next]);
		if (lp[next] >= depth[i]) is_point = 1;
	}
	if (i == s) {
		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].insert(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 get_comp(int i, vector<int> &v, int p = -1) {
	v.push_back(i);
	for (int next: tree_edges[i]) {
		if (next == p) continue;
		get_comp(next, v, i);
	}
}

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);
		if (flag) cerr << 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];
	}
	if (flag) 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;
	}
	if (flag) 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;
	for (int i = 0; i < n; i++) {
		if (!vis[i]) find_cut(i, i);
	}
	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) {
		if (flag) cout << v << endl;
		print(bccs_in[v]);
		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);
			ll csize = bcc_sz[next];
			ans += csize*(csize-1);
		}
		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);
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		rts.push_back(make_decomp(i));
		vector<int> v;
		get_comp(i, v);
		comps.push_back(v);
	}
	fill(vis, vis+n, 0);
	if (flag) cerr << endl;
	for (int rt: rts) make_ans(rt);
	for (vector<int> comp: comps) {
		ll p2sum = 0;
		ll over_sum = 0;
		ll ex = 0;
		for (int i: comp) {
			ll cur = bcc_sz[i];
			p2sum += cur*(cur-1);
			over_sum += cur;
			ex += (cur+2)*cur*(cur-1);
		}
		ans += 2*p2sum*over_sum-ex;
	}
	cout << ans << "\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Correct 11 ms 22268 KB Output is correct
4 Correct 14 ms 22356 KB Output is correct
5 Correct 12 ms 22228 KB Output is correct
6 Correct 13 ms 22168 KB Output is correct
7 Runtime error 639 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Correct 11 ms 22268 KB Output is correct
4 Correct 14 ms 22356 KB Output is correct
5 Correct 12 ms 22228 KB Output is correct
6 Correct 13 ms 22168 KB Output is correct
7 Runtime error 639 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 38788 KB Output is correct
2 Correct 104 ms 39836 KB Output is correct
3 Incorrect 194 ms 44656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 22484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 228 ms 48828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 22484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 231 ms 48828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Correct 11 ms 22268 KB Output is correct
4 Correct 14 ms 22356 KB Output is correct
5 Correct 12 ms 22228 KB Output is correct
6 Correct 13 ms 22168 KB Output is correct
7 Runtime error 639 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Correct 11 ms 22268 KB Output is correct
4 Correct 14 ms 22356 KB Output is correct
5 Correct 12 ms 22228 KB Output is correct
6 Correct 13 ms 22168 KB Output is correct
7 Runtime error 639 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -