oj.uz

Submission #388436

# Submission time Handle Problem Language Result Execution time Memory
388436 2021-04-11T13:52:14 Z milleniumEeee Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 36128 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:179:8: warning: unused variable 'cycle_size' [-Wunused-variable]
  179 |    int cycle_size = szof(cycle[ind[v]]);
      |        ^~~~~~~~~~
count_triplets.cpp:86:6: warning: unused variable 'before_ans' [-Wunused-variable]
   86 |  int before_ans = ans;
      |      ^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 4 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 1093 ms 23732 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 7512 KB Output is correct
2 Correct 5 ms 7500 KB Output is correct
3 Correct 5 ms 7492 KB Output is correct
4 Correct 5 ms 7628 KB Output is correct
5 Correct 5 ms 7628 KB Output is correct
6 Correct 5 ms 7628 KB Output is correct
7 Correct 5 ms 7628 KB Output is correct
8 Correct 5 ms 7628 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 5 ms 7500 KB Output is correct
11 Correct 6 ms 7628 KB Output is correct
12 Correct 5 ms 7504 KB Output is correct
13 Correct 5 ms 7516 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7556 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 5 ms 7500 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 5 ms 7556 KB Output is correct
20 Correct 6 ms 7500 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 27952 KB Output is correct
2 Correct 181 ms 28080 KB Output is correct
3 Correct 194 ms 27968 KB Output is correct
4 Correct 191 ms 27956 KB Output is correct
5 Correct 189 ms 27960 KB Output is correct
6 Correct 281 ms 36128 KB Output is correct
7 Correct 232 ms 33872 KB Output is correct
8 Correct 207 ms 32196 KB Output is correct
9 Correct 207 ms 30808 KB Output is correct
10 Correct 183 ms 27908 KB Output is correct
11 Correct 179 ms 27796 KB Output is correct
12 Correct 184 ms 27972 KB Output is correct
13 Correct 198 ms 27752 KB Output is correct
14 Correct 160 ms 26708 KB Output is correct
15 Correct 142 ms 25600 KB Output is correct
16 Correct 106 ms 21692 KB Output is correct
17 Correct 175 ms 29652 KB Output is correct
18 Correct 129 ms 29048 KB Output is correct
19 Correct 125 ms 29048 KB Output is correct
20 Correct 129 ms 28660 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7512 KB Output is correct
2 Correct 5 ms 7492 KB Output is correct
3 Correct 6 ms 7500 KB Output is correct
4 Correct 6 ms 7500 KB Output is correct
5 Correct 5 ms 7500 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 5 ms 7384 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 5 ms 7384 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 7500 KB Output is correct
13 Correct 5 ms 7500 KB Output is correct
14 Correct 5 ms 7512 KB Output is correct
15 Correct 6 ms 7500 KB Output is correct
16 Incorrect 6 ms 7456 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 27992 KB Output is correct
2 Correct 194 ms 27752 KB Output is correct
3 Correct 184 ms 24140 KB Output is correct
4 Correct 204 ms 20968 KB Output is correct
5 Correct 112 ms 18296 KB Output is correct
6 Correct 106 ms 17324 KB Output is correct
7 Correct 93 ms 16832 KB Output is correct
8 Correct 113 ms 16364 KB Output is correct
9 Correct 110 ms 16224 KB Output is correct
10 Correct 98 ms 15940 KB Output is correct
11 Correct 118 ms 15780 KB Output is correct
12 Correct 353 ms 15588 KB Output is correct
13 Correct 717 ms 15556 KB Output is correct
14 Execution timed out 1095 ms 17004 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 4 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -