Submission #411280

#	Time	Username	Problem	Language	Result	Execution time	Memory
411280		penguinhacker	Duathlon (APIO18_duathlon)	C++14	31 / 100	101 ms	26592 KiB

count_triplets

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

#define ll long long
#define ar array

const int mxN=1e5;
int n, m, tin[mxN], low[mxN], t, who[mxN], cc;
vector<int> adj1[mxN], adj2[mxN], cmp[mxN];
stack<int> st;
vector<ar<int, 2>> br;
ll n2, sz[mxN], ans, dp[mxN];

void make(int u) {
	while(cmp[cc].empty()||cmp[cc].back()^u) {
		cmp[cc].push_back(st.top());
		who[st.top()]=cc;
		st.pop();
	}
	sz[cc]=cmp[cc].size();
	++cc;
}

void dfs1(int u, int p=-1) {
	tin[u]=low[u]=++t;
	++n2;
	st.push(u);
	for (int v : adj1[u]) {
		if (v==p)
			continue;
		if (!tin[v]) {
			dfs1(v, u);
			low[u]=min(low[u], low[v]);
			if (low[v]>tin[u]) { //bridge
				br.push_back({u, v});
				make(v);
			}
		} else
			low[u]=min(low[u], tin[v]);
	}
}

void dfs2(int u) {
	dp[u]=sz[u];
	for (int v : adj2[u]) {
		dfs2(v);
		dp[u]+=dp[v];
		ans-=dp[v]*sz[u]*(dp[v]-1); // v->u->v
		ans-=2*dp[v]*(sz[u]-1);
		ans-=(n2-dp[v])*sz[v]*(n2-dp[v]-1); // u->v->u
		ans-=2*(n2-dp[v])*(sz[v]-1);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<m; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj1[u].push_back(v);
		adj1[v].push_back(u);
	}
	for (int i=0; i<n; ++i) {
		if (tin[i])
			continue;
		dfs1(i);
		make(i);
		while(br.size()) {
			ar<int, 2> a=br.back();
			br.pop_back();
			adj2[who[a[0]]].push_back(who[a[1]]);
		}
		ans+=n2*(n2-1)*(n2-2);
		dfs2(who[i]);
		n2=0;
	}
	cout << ans;
	return 0;
}

• 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