oj.uz

Submission #387988

# Submission time Handle Problem Language Result Execution time Memory
387988 2021-04-09T16:26:47 Z milleniumEeee Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 34940 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];
	}
}

int get_mult(vector <int> &vec) {
	int res = 0;
	int before = 0;
	for (int el : vec) {
		res += before * el;
		before += el;
	}
	return res * 2;
}

void calc_ans(int v, int par) {
	int before_ans = ans;
	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 here1 = 0;
			bool flag = (v == 7);
			for (int c : cycle[ind[v]]) {
				if (!have(c)) {
					ans += kek;
					here1 += kek;
					if (flag) {
						//cout << "no " << c << " " << kek << endl;
					}
				} else {
					vector <int> my_sub;
					for (int to : g[c]) {
						if (ind[to] != ind[c]) {
							int need = cycle[ind[to]][0];
							if (need == par) {
								my_sub.pb(sub[root] - sub[v]);								
							} else {
								my_sub.pb(sub[need]);
							}
						}
					}
					ans += kek + get_mult(my_sub);
					here1 += kek + get_mult(my_sub);
					if (flag) {
						//cout << "yes " << c << " " << kek + get_mult(my_sub) << endl;
					}
				}
			}
			if (v == 7) {
				//cout << "here1: " << here1 << endl;
			}
		}
		// 2 in cycle
		{	
			int here2 = 0;
			int other = n - szof(cycle[ind[v]]);
			int cycle_size = szof(cycle[ind[v]]);
			for (int c : cycle[ind[v]]) {
				for (int s : cycle[ind[v]]) {
					if (c != s) {
						ans += (other - calc_my(s)) * 2;
						here2 += (other - calc_my(s)) * 2;
					}
				}
			}
			if (v == 6) {
				//cout << "here2: " << here2 << endl;
			}
		}
		// 3 in cycle
		{
			int siz = szof(cycle[ind[v]]);
			ans += siz * (siz - 1) * (siz - 2);
			if (v == 6) {
				//cout << "here3: " << siz * (siz - 1) * (siz - 2) << endl;
			}
		}
	}
	//cout << v << ": " << ans - before_ans << endl;
	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;
}

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

Compilation message

count_triplets.cpp: In function 'void calc_ans(long long int, long long int)':
count_triplets.cpp:180:8: warning: unused variable 'cycle_size' [-Wunused-variable]
  180 |    int cycle_size = szof(cycle[ind[v]]);
      |        ^~~~~~~~~~
count_triplets.cpp:87:6: warning: unused variable 'before_ans' [-Wunused-variable]
   87 |  int before_ans = ans;
      |      ^~~~~~~~~~

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 1091 ms 22600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 5 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 5 ms 7628 KB Output is correct
7 Correct 7 ms 7628 KB Output is correct
8 Correct 6 ms 7628 KB Output is correct
9 Correct 6 ms 7500 KB Output is correct
10 Correct 6 ms 7500 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7500 KB Output is correct
13 Correct 6 ms 7500 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7504 KB Output is correct
16 Correct 5 ms 7528 KB Output is correct
17 Correct 5 ms 7500 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct
19 Correct 6 ms 7592 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 279 ms 26744 KB Output is correct
2 Correct 267 ms 26696 KB Output is correct
3 Correct 208 ms 26692 KB Output is correct
4 Correct 244 ms 26704 KB Output is correct
5 Correct 265 ms 26768 KB Output is correct
6 Correct 249 ms 34940 KB Output is correct
7 Correct 248 ms 32580 KB Output is correct
8 Correct 343 ms 31016 KB Output is correct
9 Correct 222 ms 29508 KB Output is correct
10 Correct 211 ms 26652 KB Output is correct
11 Correct 283 ms 26688 KB Output is correct
12 Correct 221 ms 26832 KB Output is correct
13 Correct 214 ms 26676 KB Output is correct
14 Correct 205 ms 25732 KB Output is correct
15 Correct 207 ms 24608 KB Output is correct
16 Correct 99 ms 20868 KB Output is correct
17 Correct 134 ms 28660 KB Output is correct
18 Correct 140 ms 27960 KB Output is correct
19 Correct 136 ms 28028 KB Output is correct
20 Correct 142 ms 27660 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 5 ms 7500 KB Output is correct
4 Correct 5 ms 7496 KB Output is correct
5 Correct 5 ms 7392 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7628 KB Output is correct
13 Correct 5 ms 7500 KB Output is correct
14 Correct 6 ms 7500 KB Output is correct
15 Correct 6 ms 7500 KB Output is correct
16 Incorrect 6 ms 7500 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 26772 KB Output is correct
2 Correct 266 ms 26536 KB Output is correct
3 Correct 200 ms 22732 KB Output is correct
4 Correct 179 ms 21080 KB Output is correct
5 Correct 171 ms 18344 KB Output is correct
6 Correct 123 ms 17348 KB Output is correct
7 Correct 106 ms 16848 KB Output is correct
8 Correct 110 ms 16368 KB Output is correct
9 Correct 122 ms 16196 KB Output is correct
10 Correct 128 ms 16020 KB Output is correct
11 Correct 123 ms 15684 KB Output is correct
12 Correct 359 ms 15588 KB Output is correct
13 Correct 711 ms 15472 KB Output is correct
14 Execution timed out 1098 ms 16964 KB Time limit exceeded
15 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 -