Submission #387972

#	Time	Username	Problem	Language	Result	Execution time	Memory
387972		milleniumEeee	Duathlon (APIO18_duathlon)	C++14	23 / 100	1094 ms	35692 KiB

count_triplets

#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 (stderr)

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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10