oj.uz

Submission #387935

# Submission time Handle Problem Language Result Execution time Memory
387935 2021-04-09T14:24:17 Z milleniumEeee Duathlon (APIO18_duathlon) C++17
0 / 100
 1000 ms 38724 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;

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

int root; // корень сжатого дерева
void calc_ans(int v, int par) {
	int cur_add = 0;
	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();
		cur_add += calc_other();
	} else {
		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;
					cur_add += between;
				} else {
					ans += kek;
					cur_add += 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;
					cur_add += my * (cycle_size - 1) * 2;
				} else {
					int nw = 0;
					for (int f : cycle[ind[v]]) {
						if (c != f) {
							ans += (other - calc_my(f)) * 2;
							cur_add += (other - calc_my(f)) * 2;
							nw += (other - calc_my(f)) * 2;
						}
					}
				}
			}
		}
		// 3 in cycle
		{
			int siz = szof(cycle[ind[v]]);
			ans += siz * (siz - 1) * (siz - 2);
			cur_add += 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);
	}
	precalc(1, -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);
	}
	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 Incorrect 5 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 22472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 26672 KB Output is correct
2 Correct 224 ms 27844 KB Output is correct
3 Correct 241 ms 27968 KB Output is correct
4 Correct 283 ms 27888 KB Output is correct
5 Correct 225 ms 27908 KB Output is correct
6 Correct 291 ms 38724 KB Output is correct
7 Correct 333 ms 35400 KB Output is correct
8 Correct 238 ms 33480 KB Output is correct
9 Correct 267 ms 31496 KB Output is correct
10 Incorrect 204 ms 28028 KB Output isn't correct
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 6 ms 7560 KB Output is correct
3 Incorrect 6 ms 7500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 26692 KB Output is correct
2 Correct 236 ms 27628 KB Output is correct
3 Incorrect 246 ms 24024 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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