Submission #565274

#	Time	Username	Problem	Language	Result	Execution time	Memory
565274		S2speed	Duathlon (APIO18_duathlon)	C++17	100 / 100	211 ms	36632 KiB

count_triplets

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 2e5 + 17 , inf = 2e16;

ll n , m;
vector<ll> adj[maxn] , cdj[maxn];
bitset<maxn> mark , bor , bst;
ll dis[maxn] , dep = 0 , hb[maxn] , z[maxn] , sz , ans = 0 , o , cs[maxn] , pr[maxn];
vector<pll> b;

void bDFS(ll r){
	mark[r] = true;
	dis[r] = dep++;
	bool f = false;
	for(auto i : adj[r]){
		if(dis[i] == dep - 2) continue;
		if(mark[i]){
			hb[r] = min(hb[r] , dis[i]);
			continue;
		}
		pr[i] = r;
		bDFS(i);
		hb[r] = min(hb[r] , hb[i]);
		f |= (hb[i] >= dep - 1);
	}
	bor[r] = f;
	dep--;
	return;
}

void cDFS(ll r , ll ban){
	bst[r] = true;
	if(bor[r]){
		cdj[o].push_back(r); cdj[r].push_back(o);
	} else {
		cs[o]++;
	}
	for(auto i : adj[r]){
		if(i == pr[r] || i == ban) continue;
		if(bst[i]) continue;
		cDFS(i , ban);
	}
	return;
}

void zDFS(ll r , ll par){
	mark[r] = true;
	if(r < n){
		z[r] = 1;
	} else {
		z[r] = cs[r];
	}
	for(auto i : cdj[r]){
		if(i == par) continue;
		zDFS(i , r);
		z[r] += z[i];
	}
	return;
}

void aDFS(ll r , ll par){
	for(auto i : cdj[r]){
		if(i == par) continue;
		aDFS(i , r);
	}
	if(r < n) return;
	ll h = 0;
	for(auto i : cdj[r]){
		if(i == par) continue;
		h += z[i] * (z[i] - 1);
	}
	h += (sz - z[r]) * (sz - z[r] - 1);
	ans -= (cs[r] + sze(cdj[r]) - 1) * h;
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(hb , 63 , sizeof(hb));
	memset(dis , 63 , sizeof(dis));
	memset(cs , 0 , sizeof(cs));
	memset(pr , -1 , sizeof(pr));
	cin>>n>>m;
	for(ll i = 0 ; i < m ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		adj[v].push_back(u); adj[u].push_back(v);
	}
//	cout<<"----------------------------------\n";
	for(ll i = 0 ; i < n ; i++){
		if(mark[i]) continue;
		bDFS(i);
	}
	for(ll i = 0 ; i < n ; i++){
		if(!bor[i]) continue;
		b.push_back({dis[i] , i});
	}
	sort(all(b) , greater<pll>());
	o = n;
	for(auto p : b){
		ll r = p.second;
		for(auto i : adj[r]){
			if(i == pr[r]) continue;
			if(pr[i] != r) continue;
			if(hb[i] >= dis[r]){
//				cout<<r<<' '<<i<<'\n';
				cDFS(i , r);
				cdj[o].push_back(r); cdj[r].push_back(o);
				o++;
			}
		}
	}
//	for(ll i = 0 ; i < n ; i++){
//		cout<<pr[i]<<' ';
//	}
//	cout<<'\n';
//	for(ll i = n ; i < o ; i++){
//		cout<<cs[i]<<'\n';
//		for(auto j : cdj[i]){
//			cout<<j<<' ';
//		}
//		cout<<'\n';
//	}
	mark.reset();
	for(ll i = 0 ; i < n ; i++){
		if(!bor[i]) continue;
		if(mark[i]) continue;
		zDFS(i , -1);
		sz = z[i];
		ans += sz * (sz - 1) * (sz - 2);
		aDFS(i , -1);
	}
	cout<<ans<<'\n';
	return 0;
}

/*
6 6
1 2
2 3
3 4
4 5
5 2
4 6
*/

• 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