oj.uz

Submission #387942

# Submission time Handle Problem Language Result Execution time Memory
387942 2021-04-09T14:38:24 Z milleniumEeee Duathlon (APIO18_duathlon) C++14
0 / 100
 1000 ms 45968 KB 
#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define int long long
using namespace std;

const int MAXN = (int)1e5 + 5;

vector <int> g[MAXN];
vector <int> G[MAXN]; // кактусовый граф

int pr[MAXN];
bool used[MAXN];
bool black[MAXN];
vector <int> cycle[MAXN];
int ind[MAXN], cur_ind;

pii joop(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	return {x, y};
}

void precalc(int v, int par) {
	pr[v] = par;
	used[v] = 1;
	for (int to : g[v]) {
		if (to == par) {
			continue;
		}
		if (used[to] && !black[to]) {
			cur_ind++;
			int fn = v;
			while (fn != to) {
				cycle[cur_ind].pb(fn);
				fn = pr[fn];
			}
			cycle[cur_ind].pb(fn);
			for (int el : cycle[cur_ind]) {
				black[el] = 1;
				ind[el] = cur_ind;
			}
		} else if (!used[to]) {
			precalc(to, v);
		}
	}
}

int ans = 0;
int sub[MAXN];
int n, m;


int root; // корень сжатого дерева

bool was[MAXN];

void calc_sub(int v, int par) {
	was[v] = 1;
	sub[v] = szof(cycle[ind[v]]);
	for (int to : G[v]) {
		if (to == par) {
			continue;
		}
		calc_sub(to, v);
		sub[v] += sub[to];
	}
}

void calc_ans(int v, int par) {
	auto calc_other = [&]() {
		vector <int> vec;
		for (int to : G[v]) {
			if (to == par) {
				continue;
			}
			vec.pb(sub[to]);
		}
		if (v != root) {
			vec.pb(sub[root] - sub[v]);
		}
		int sum = 0;
		int before = 0;
		for (int el : vec) {
			sum += before * el;
			before += el;
		}
		return sum * 2;
	};
	if (!black[v]) {
		ans += calc_other();
	} else {
		assert(false);
		auto calc_my = [&](int vrt) {
			int my = 0;
			for (int to : g[vrt]) {
				if (ind[vrt] != ind[to]) {
					int need = cycle[ind[to]][0];
					if (need == par) {
						my += n - sub[v];
					} else {
						my += sub[need];
					}
				}
			}
			return my;
		};
		auto have = [&](int v) {
			bool flag = (szof(g[v]) > 2);
			return flag;
		};
		// 1 in cycle 
		{
			int kek = 0;
			vector <int> vec;
			for (int vrt : cycle[ind[v]]) {
				if (have(vrt)) {
					vec.pb(calc_my(vrt));
				}
			}
			int before = 0;
			for (int el : vec) {
				kek += el * before;
				before += el;
			}
			kek *= 2;
			int between = calc_other();
			for (int c : cycle[ind[v]]) {
				if (have(c)) {
					ans += between;
				} else {
					ans += kek;
				}
			}
		}
		// 2 in cycle
		{	
			int other = n - szof(cycle[ind[v]]);
			int cycle_size = szof(cycle[ind[v]]);
			for (int c : cycle[ind[v]]) {
				if (have(c)) {
					int my = calc_my(c);
					ans += my * (cycle_size - 1) * 2;
				} else {
					for (int f : cycle[ind[v]]) {
						if (c != f) {
							ans += (other - calc_my(f)) * 2;
						}
					}
				}
			}
		}
		// 3 in cycle
		{
			int siz = szof(cycle[ind[v]]);
			ans += siz * (siz - 1) * (siz - 2);
		}
	}
	for (int to : G[v]) {
		if (to == par) {
			continue;
		}
		calc_ans(to, v);
	}
}

signed main() {
	fastInp;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	for (int i = 1; i <= n; i++) {
		if (!used[i]) {
			precalc(i, -1);			
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!black[i]) {
			ind[i] = ++cur_ind;
			cycle[ind[i]].pb(i);
		}
	}
	set <pii> st;
	for (int i = 1; i <= n; i++) {
		for (int to : g[i]) {
			if (ind[i] != ind[to]) {
				st.insert(joop(ind[i], ind[to]));
			}
		}
	}
	for (auto el : st) {
		int x = cycle[el.fr][0];
		int y = cycle[el.sc][0];
		G[x].pb(y);
		G[y].pb(x);
	}
	for (int i = 1; i <= cur_ind; i++) {
		root = cycle[i][0];
		if (!was[root]) {
			root = cycle[1][0];
			calc_sub(root, -1);
			calc_ans(root, -1);
		}
	}
	cout << ans << endl;
}

/*
10 11
1 2
2 3
2 4
4 3
1 5
5 6
6 9
6 10
5 7 
7 8
5 8
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 14792 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 14792 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 45496 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 6 ms 7500 KB Output is correct
3 Correct 6 ms 7500 KB Output is correct
4 Correct 5 ms 7628 KB Output is correct
5 Correct 6 ms 7628 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7628 KB Output is correct
8 Correct 6 ms 7500 KB Output is correct
9 Correct 6 ms 7500 KB Output is correct
10 Incorrect 14 ms 7568 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 26696 KB Output is correct
2 Correct 228 ms 26708 KB Output is correct
3 Correct 213 ms 26656 KB Output is correct
4 Correct 210 ms 26692 KB Output is correct
5 Correct 209 ms 26660 KB Output is correct
6 Correct 254 ms 31520 KB Output is correct
7 Correct 282 ms 30276 KB Output is correct
8 Correct 229 ms 29248 KB Output is correct
9 Correct 225 ms 28408 KB Output is correct
10 Execution timed out 1097 ms 26736 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7500 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Runtime error 12 ms 15136 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 26736 KB Output is correct
2 Correct 227 ms 26512 KB Output is correct
3 Runtime error 185 ms 45968 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 14792 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 14792 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -