oj.uz

Submission #387972

# Submission time Handle Problem Language Result Execution time Memory
387972 2021-04-09T15:31:03 Z milleniumEeee Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 35692 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) {
	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 between = calc_other();
			int here1 = 0;
			for (int c : cycle[ind[v]]) {
				if (have(c)) {
					ans += between;
					here1 += between;
				} else {
					ans += kek;
					here1 += kek;
				}
			}
			//if (v == 5) {
				//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 == 5) {
				//cout << "here2: " << here2 << endl;
			//}
		}
		// 3 in cycle
		{
			int siz = szof(cycle[ind[v]]);
			ans += siz * (siz - 1) * (siz - 2);
			if (v == 5) {
				//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;
}

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

Compilation message

count_triplets.cpp: In function 'void calc_ans(long long int, long long int)':
count_triplets.cpp:153:8: warning: unused variable 'cycle_size' [-Wunused-variable]
  153 |    int cycle_size = szof(cycle[ind[v]]);
      |        ^~~~~~~~~~
count_triplets.cpp:77:6: warning: unused variable 'before_ans' [-Wunused-variable]
   77 |  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 1094 ms 22564 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 7528 KB Output is correct
3 Correct 7 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 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 7504 KB Output is correct
13 Correct 7 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 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7512 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct
19 Correct 6 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 218 ms 26772 KB Output is correct
2 Correct 210 ms 26700 KB Output is correct
3 Correct 216 ms 26756 KB Output is correct
4 Correct 258 ms 26776 KB Output is correct
5 Correct 214 ms 26764 KB Output is correct
6 Correct 253 ms 35692 KB Output is correct
7 Correct 234 ms 33148 KB Output is correct
8 Correct 296 ms 31428 KB Output is correct
9 Correct 277 ms 29720 KB Output is correct
10 Correct 213 ms 26684 KB Output is correct
11 Correct 207 ms 26708 KB Output is correct
12 Correct 224 ms 26692 KB Output is correct
13 Correct 266 ms 26776 KB Output is correct
14 Correct 204 ms 25588 KB Output is correct
15 Correct 165 ms 24680 KB Output is correct
16 Correct 103 ms 20940 KB Output is correct
17 Correct 142 ms 28704 KB Output is correct
18 Correct 140 ms 27932 KB Output is correct
19 Correct 140 ms 27948 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 6 ms 7500 KB Output is correct
3 Incorrect 5 ms 7524 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 26780 KB Output is correct
2 Correct 231 ms 26436 KB Output is correct
3 Incorrect 211 ms 22732 KB Output isn't correct
4 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 -