Submission #49273

#	Time	Username	Problem	Language	Result	Execution time	Memory
49273		Noam527	Duathlon (APIO18_duathlon)	C++17	100 / 100	343 ms	47848 KiB

count_triplets

#include <bits/stdc++.h>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
#define yesno(X) cout << ((X) ? "YES" : "NO") << endl
#define noyes(X) cout << ((X) ? "NO" : "YES") << endl
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

struct edge {
	int to, level;
	ll size;
	edge(int tt = 0) {
		to = tt;
		level = 0;
		size = 0;
	}
};

int n, m;
vector<vector<edge>> g;
vector<int> vis, dep, low, art;

int nn, first;
vector<int> nind; // for articulation points
vector<ll> w;
ll ans = 0;
vector<vector<edge>> gg;
vector<vector<int>> comp;
vector<ll> supersum;

void newcomp(int v, int prev) {
	comp.back().push_back(v);
	for (auto &i : g[v]) {
		if (i.to != prev && i.level == 1) {
			i.level = 2;
			newcomp(i.to, v);
		}
	}
}

void dfs(int v = 0, int prev = -1, int d = 0) {
	vis[v] = 1;
	dep[v] = d;
	low[v] = d;
	for (auto &i : g[v]) {
		if (i.to != prev) {
			if (vis[i.to])
				low[v] = min(low[v], dep[i.to]);
			else {
				i.level = 1;
				dfs(i.to, v, d + 1);
				if (d <= low[i.to]) {
					art[v] = 1;
					comp.push_back(vector<int>());
					comp.back().push_back(v);
					newcomp(i.to, v);
					i.level = 2;
				}
				low[v] = min(low[v], low[i.to]);
			}
		}
	}
}

int sz(int v, int prev = -1) {
	int rtn;
	if (v < first) rtn = w[v];
	else rtn = 1;
	for (const auto &i : gg[v])
		if (i.to != prev)
			rtn += sz(i.to, v);
	return rtn;
}
int makesizes(int v, const int &tot, int prev = -1) {
	int rtn, tmp;
	if (v < first) rtn = w[v];
	else rtn = 1;
	for (auto &i : gg[v])
		if (i.to != prev) {
			tmp = makesizes(i.to, tot, v);
			rtn += tmp;
			i.size = tmp;
		}
	for (auto &i : gg[v]) {
		if (i.to == prev)
			i.size = tot - rtn;
		supersum[v] += (i.size * (i.size - 1));
	}
	return rtn;
}

void subtract(int v, const int &tot, int prev = -1) {
	vis[v] = 1;
	if (v < first) {
		for (const auto &i : gg[v]) {
			ans -= (w[v] * i.size * (i.size - 1));
		}
	}
	else {
		for (const auto &i : gg[v]) {
			ans -= (supersum[i.to] - (tot - i.size) * (tot - i.size - 1));
		}
	}
	for (const auto &i : gg[v])
		if (i.to != prev)
			subtract(i.to, tot, v);
}

void calc(int v) {
	if (vis[v]) return;
	ll tot = sz(v);
	makesizes(v, tot);
	ans += tot * (tot - 1) * (tot - 2);
	subtract(v, tot);
}

int main() {
	fast;
	cin >> n >> m;
	g.resize(n);
	vis.resize(n, 0);
	dep.resize(n, 0);
	art.resize(n, 0);
	low.resize(n, 0);
	nind.resize(n, 0);
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		--u, --v;
		g[u].push_back(edge(v));
		g[v].push_back(edge(u));
	}
	for (int i = 0; i < n; i++) {
		if (!vis[i]) dfs(i);
	}
	/*
	cout << comp.size() << " components:" << endl;
	for (const auto &i : comp) {
		for (const auto &j : i) cout << j << " "; cout << endl;
	}
	cout << "articulation points: ";
	for (int i = 0; i < n; i++) if (art[i]) cout << i << " "; cout << endl;
	*/
	first = comp.size();
	nn = first;
	for (int i = 0; i < n; i++) {
		if (art[i]) {
			nind[i] = nn++;
		}
	}
	gg.resize(nn);
	w.resize(first);
	for (int i = 0; i < comp.size(); i++) {
		w[i] = comp[i].size();
		for (const auto &j : comp[i]) 
			if (art[j]) {
				gg[i].push_back(edge(nind[j]));
				gg[nind[j]].push_back(edge(i));
				w[i]--;
			}
	}
	/*
	cout << "w" << endl;
	for (const auto &i : w) cout << i << " "; cout << endl;
	cout << "normal: " << first << " extra: " << nn - first << endl;
	for (int i = 0; i < nn; i++) {
		cout << i << ": ";
		for (const auto &j : gg[i]) cout << j.to << " "; cout << endl;
	}
	*/
	vis.resize(nn);
	supersum.resize(nn, 0);
	for (auto &i : vis) i = 0;
	for (int i = 0; i < nn; i++) calc(i);
	cout << ans << endl;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:159:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < comp.size(); i++) {
                  ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10