Submission #1201848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201848		crispxx	Duathlon (APIO18_duathlon)	C++20	31 / 100	913 ms	1114112 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

template <typename A, typename B>
bool chmin(A &a, const B &b) {
	if(a > b) {
		return a = b, true;
	}
	return false;
}

template <typename A, typename B>
bool chmax(A &a, const B &b) {
	if(a < b) {
		return a = b, true;
	}
	return false;
}

void solve() {
	int n, m; cin >> n >> m;
	
	vector<vector<int>> adj(n);
	
	vector<pair<int, int>> edges;
	
	vector<int> d(n);
	
	for(int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		adj[--u].pb(--v);
		adj[v].pb(u);
		d[u]++, d[v]++;
		edges.pb({u, v});
	}
	
	if(n <= 50) {
		auto make_path = [&](int s, int t, vector<int> &used) -> vector<int> {
			queue<int> q;
			q.emplace(s);
			vector<int> p(n, -1);
			p[s] = -2;
			while(!q.empty()) {
				int v = q.front();
				q.pop();
				if(v == t) {
					vector<int> path;
					while(t >= 0) {
						path.pb(t);
						t = p[t];
					}
					return path;
				}
				for(auto to : adj[v]) {
					if(p[to] == -1 && !used[to]) {
						p[to] = v;
						q.emplace(to);
					}
				}
			}
			return {};
		};
		
		auto is = [&](int i, int j, int v) {
			vector<int> used(n);
			auto got = make_path(v, i, used);
			if(got.empty()) return false;
			for(auto x : got) used[x] = true;
			got = make_path(v, j, used);
			return !got.empty();
		};
		
		int ans = 0;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				for(int v = 0; v < n; v++){
					if(v == i || v == j || i == j) continue;
					if(is(i, j, v)) {
						// cout << i + 1 << ' ' << v + 1 << ' ' << j + 1 << nl;
						ans += 1;
					}
				}
			}
		}
		cout << ans << nl;
		return;
	}
	
	int s3 = 1;
	
	for(int i = 0; i < n; i++) {
		if(d[i] > 2) {
			s3 = false;   
			break;
		}
	}
	
	if(s3) {
		vector<int> used(n);
		int cnt = 0, is = 0;
		auto dfs = [&](auto &&self, int v, int p) -> void {
			used[v] = true;
			cnt++;
			for(auto to : adj[v]) {
				if(to == p) continue;
				if(used[to]) {
					is = 1;
					continue;
				}
				self(self, to, v);
			}
		};
		
		int ans = 0;
		
		for(int i = 0; i < n; i++) {
			if(!used[i]) {
				cnt = 0;
				is = 0;
				dfs(dfs, i, -1);
				if(is) {
					ans += cnt * (cnt - 2) * (cnt - 1);
				} else {
					for(int j = 0; j < cnt; j++) {
						ans += 2 * j * (cnt - 1 - j);
					}
				}
			}
		}
		
		cout << ans << nl;
		return;
	}
	
	auto solve1 = [&]() {
		int ans = 0;
		
		for(int u = 0; u < n; u++) {
			queue<int> q;
			vector<int> d(n, -1), sum(n);
			q.emplace(u);
			d[u] = 0;
			while(!q.empty()) {
				int v = q.front();
				q.pop();
				ans += sum[v];
				for(auto to : adj[v]) {
					if(d[to] == -1) {
						d[to] = d[v] + 1;
						sum[to] += d[v];
						q.emplace(to);
					}
				}
			}
		}
		
		return ans;
	};
	
	vector<int> s(n, 1), used(n), par(n);
	
	int ans = 0;
	
	auto dfs = [&](auto &&self, int v, int p, vector<int> &output) -> void {
		used[v] = true;
		par[v] = p;
		for(auto to : adj[v]) {
			if(to == p) continue;
			self(self, to, v, output);
			s[v] += s[to];
		}
		output.pb(v);
	};
	
	vector<int> output;
	
	auto solve2 = [&]() {
		for(int i = 0; i < n; i++) {
			if(!used[i]) {
				output.clear();
				dfs(dfs, i, -1, output);
				for(auto v : output) {
					for(auto to : adj[v]) {
						if(to == par[v]) {
							ans += (s[v] - 1) * (s[i] - s[v]);
						} else ans += s[to] * (s[i] - 1 - s[to]);
					}
				}
			}
		}
	};
	
	auto print = [&](int x) {
		cout << x << nl;
	};
	
	solve2();
	
	cout << ans << nl;
}

/**
4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2

**/

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 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