oj.uz

Submission #387947

# Submission time Handle Problem Language Result Execution time Memory
387947 2021-04-09T14:54:28 Z milleniumEeee Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 37404 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[ind[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[ind[root]]) {
			calc_sub(root, -1);
			calc_ans(root, -1);
		}
	}
	cout << ans << endl;
}

/*
6 4
2 1
3 1
4 5
6 4
*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 7384 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 1085 ms 22540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 6 ms 7628 KB Output is correct
5 Correct 6 ms 7628 KB Output is correct
6 Correct 6 ms 7628 KB Output is correct
7 Correct 6 ms 7632 KB Output is correct
8 Correct 6 ms 7628 KB Output is correct
9 Correct 6 ms 7628 KB Output is correct
10 Correct 6 ms 7500 KB Output is correct
11 Correct 6 ms 7500 KB Output is correct
12 Correct 6 ms 7536 KB Output is correct
13 Correct 6 ms 7500 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 6 ms 7500 KB Output is correct
16 Correct 6 ms 7500 KB Output is correct
17 Correct 6 ms 7540 KB Output is correct
18 Correct 6 ms 7500 KB Output is correct
19 Correct 5 ms 7500 KB Output is correct
20 Correct 5 ms 7500 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 26844 KB Output is correct
2 Correct 259 ms 26828 KB Output is correct
3 Correct 271 ms 26704 KB Output is correct
4 Correct 216 ms 26824 KB Output is correct
5 Correct 238 ms 26676 KB Output is correct
6 Correct 271 ms 37404 KB Output is correct
7 Correct 276 ms 34352 KB Output is correct
8 Correct 258 ms 32280 KB Output is correct
9 Correct 250 ms 30348 KB Output is correct
10 Correct 242 ms 26880 KB Output is correct
11 Correct 220 ms 26784 KB Output is correct
12 Correct 254 ms 26692 KB Output is correct
13 Correct 278 ms 26764 KB Output is correct
14 Correct 189 ms 25668 KB Output is correct
15 Correct 165 ms 24572 KB Output is correct
16 Correct 112 ms 20920 KB Output is correct
17 Correct 149 ms 28596 KB Output is correct
18 Correct 147 ms 28036 KB Output is correct
19 Correct 148 ms 28016 KB Output is correct
20 Correct 156 ms 27544 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7500 KB Output is correct
2 Correct 6 ms 7500 KB Output is correct
3 Incorrect 5 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 256 ms 26768 KB Output is correct
2 Correct 323 ms 26592 KB Output is correct
3 Incorrect 243 ms 22644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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