Submission #50030

#	Time	Username	Problem	Language	Result	Execution time	Memory
50030		tmwilliamlin168	Duathlon (APIO18_duathlon)	C++14	0 / 100	325 ms	54392 KiB

count_triplets

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

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int mxN=1e5;
int n, m, dt=1, tin[mxN], low[mxN], sth, bccI, rt[2*mxN];
pii st[2*mxN];
ll sz1[2*mxN], sz2[mxN], ans;
vector<int> adj1[mxN], adj2[2*mxN];
set<int> bccs[mxN];
bool vis[2*mxN];

void dfs1(int u, int p) {
	tin[u]=low[u]=dt++;
	for(int v : adj1[u]) {
		if(!tin[v]) {
			int lsth=sth;
			st[sth++]={u, v};
			dfs1(v, u);
			low[u]=min(low[v], low[u]);
			if(low[v]>=tin[u]) {
				while(sth>lsth) {
					--sth;
					bccs[bccI].insert(st[sth].fi);
					bccs[bccI].insert(st[sth].se);
				}
				++bccI;
			}
		} else if(v!=p)
			low[u]=min(tin[v], low[u]);
	}
}

void dfs2(int u, int p) {
	sz1[u]=u<n;
	for(int v : adj2[u]) {
		if(v==p)
			continue;
		rt[v]=rt[u];
		dfs2(v, u);
		sz1[u]+=sz1[v];
	}
}

void dfs3(int u, int p) {
//	cout << "d2 " << u << endl;
	vis[u]=1;
	ll n2=sz1[rt[u]]-adj2[u].size();
	for(int v : adj2[u]) {
		if(v==p)
			continue;
		dfs3(v, u);
		n2-=sz1[v]-1;
		if(u>=n)
			ans+=2*(sz1[v]-sz2[v]+adj2[u].size()-2)*n2;
	}
	if(u<n) {
		n2=sz1[u]-sz2[u]+adj2[p].size()-2;
		for(int v : adj2[u]) {
			if(v==p)
				continue;
			n2-=sz1[v]-adj2[v].size()+1;
			ans+=2*(sz1[v]-adj2[v].size()+1)*n2;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	while(m--) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj1[u].push_back(v);
		adj1[v].push_back(u);
	}
	dfs1(0, -1);
	for(int i=0; i<bccI; ++i) {
		for(int j : bccs[i]) {
			adj2[j].push_back(i+n);
			adj2[i+n].push_back(j);
			sz2[j]+=bccs[i].size()-1;
		}
	}
	for(int i=0; i<bccI; ++i) {
		ll bs=bccs[i].size();
		if(!rt[i+n]) {
			rt[i+n]=i+n;
			dfs2(i+n, -1);
		}
		ans+=bs*(bs-1)*(bs-2)+2*(bs-1)*(bs-1)*(sz1[rt[i+n]]-bs)+bs*(bs-1)*(bs-1);
	}
	for(int i=0; i<n; ++i)
		ans-=sz2[i]*sz2[i];
//	cout << bccI << " " << ans << endl;
//	for(int i=0; i<n; ++i)
//		cout << sz2[i] << " ";
//	cout << endl;
	for(int i=0; i<bccI; ++i)
		if(!vis[i+n])
			dfs3(i+n, -1);
	cout << ans;
}

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