Submission #48968

#	Time	Username	Problem	Language	Result	Execution time	Memory
48968		polyfish	Duathlon (APIO18_duathlon)	C++14	69 / 100	1077 ms	36024 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}

bool maximize(int &a, int b) {if (a>=b) return false; a = b; return true;}

const int maxn = 100002;

int n, m, ID[maxn];
vector<int> g[maxn], node;
vector<pair<int, int> > edge;
bool visited[maxn];

class solver {	//Solve for connected graph
public:
	vector<int> g[maxn], BCC[maxn], tmp;
	int n, nTime, nBCC, num[maxn], low[maxn], nChild[maxn];
	int par[maxn], lastComponent[maxn];
	stack<int> st;
	map<int, int> f[maxn];

	void init(int _n, vector<pair<int, int> > e) {
		n = _n;
		for (int i=1; i<=n; ++i) {
			g[i].clear();
			BCC[i].clear();
			f[i].clear();
		}
		for (int i=0; i<e.size(); ++i) {
			g[e[i].first].push_back(e[i].second);
			g[e[i].second].push_back(e[i].first);
		}
		nBCC = 0;
		nTime = 0;
		while (st.size())
			st.pop();
		memset(lastComponent, 0, sizeof(lastComponent));
		memset(num, 0, sizeof(num));
	}

	int dfs(int u) {
		num[u] = low[u] = ++nTime;
		nChild[u] = 1;
		int tmp = 0;
		for (int i=0; i<g[u].size(); ++i) {
			int v = g[u][i];
			if (num[v])
				low[u] = min(low[u], num[v]);
			else {
				st.push(u);
				nChild[u] += dfs(v);
				low[u] = min(low[u], low[v]);
				if (low[v]>=num[u]) {
					tmp += nChild[v];
					++nBCC;
					while (true) {
						int t = st.top(); st.pop();
						if (maximize(lastComponent[t], nBCC))
							BCC[nBCC].push_back(t);
						if (t==u)
							break;
					}
					f[u][nBCC] = nChild[v] + 1;
				}
			}
		}
		par[u] = n - tmp - 1;
		st.push(u);
		return nChild[u];
	}

	int64_t solve() {
		if (n==1)
			return 0;
		int64_t res = 0;
		for (int i=1; i<=nBCC; ++i) {
			int sz = BCC[i].size();
			tmp.clear();
			for (int j=0; j<sz; ++j) {
				int u = BCC[i][j];
				if (f[u].count(i))
					tmp.push_back(n-f[u][i]);
				else
					tmp.push_back(n-par[u]-1);
			}
			res += 1LL*sz*(sz-1)*(sz-2);
			int64_t T = 0, sqrT = 0;
			for (int i=0; i<tmp.size(); ++i) {
				res += (1LL*(n-sz)*(sz-1) - (n-sz-tmp[i]));
				res += (1LL*(n-sz-tmp[i])*(sz-1) - (n-sz-tmp[i]));
				T += tmp[i];
				sqrT += 1LL*tmp[i]*(tmp[i]-1);
			}
			for (int i=0; i<tmp.size(); ++i) {
				res += (1LL*(T-tmp[i])*(T-tmp[i]-1) - sqrT + 1LL*tmp[i]*(tmp[i]-1));
				res += 1LL*tmp[i]*(T-tmp[i]);
			}
		}
		return res;
	}
} S;

void visit(int u) {
	node.push_back(u);
	visited[u] = true;
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i];
		edge.push_back(make_pair(max(u, v), min(u, v)));
		if (!visited[v]) {
			visit(v);
		}
	}
}

void make_graph() {
	int cnt = 0;
	sort(node.begin(), node.end());
	sort(edge.begin(), edge.end());
	edge.resize(unique(edge.begin(), edge.end())-edge.begin());
	for (int i=0; i<node.size(); ++i) {
		ID[node[i]] = i+1;
	}
	for (int i=0; i<edge.size(); ++i) {
		edge[i].first = ID[edge[i].first];
		edge[i].second = ID[edge[i].second];
	}
	//PR0(node, node.size());
	//for (int i=0; i<edge.size(); ++i)
	//	cerr << edge[i].first << ' ' << edge[i].second << '\n';
}

int main() {
	//freopen("count-triplets.inp", "r", stdin);
	//freopen("count-triplets.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i=1; i<=m; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int64_t res = 0;
	for (int i=1; i<=n; ++i) {
		if (!visited[i]) {
			edge.clear();
			node.clear();
			visit(i);
			make_graph();
			S.init(node.size(), edge);
			S.dfs(1);
			res += S.solve();
		}
	}
	cout << res;
}

Compilation message (stderr)

count_triplets.cpp: In member function 'void solver::init(int, std::vector<std::pair<int, int> >)':
count_triplets.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<e.size(); ++i) {
                 ~^~~~~~~~~
count_triplets.cpp: In member function 'int solver::dfs(int)':
count_triplets.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<g[u].size(); ++i) {
                 ~^~~~~~~~~~~~
count_triplets.cpp: In member function 'int64_t solver::solve()':
count_triplets.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0; i<tmp.size(); ++i) {
                  ~^~~~~~~~~~~
count_triplets.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0; i<tmp.size(); ++i) {
                  ~^~~~~~~~~~~
count_triplets.cpp: In function 'void visit(int)':
count_triplets.cpp:110:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void make_graph()':
count_triplets.cpp:124:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<node.size(); ++i) {
                ~^~~~~~~~~~~~
count_triplets.cpp:127:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<edge.size(); ++i) {
                ~^~~~~~~~~~~~
count_triplets.cpp:120:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 0;
      ^~~

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