Submission #732822

#	Time	Username	Problem	Language	Result	Execution time	Memory
732822		sentheta	Duathlon (APIO18_duathlon)	C++17	10 / 100	1081 ms	28460 KiB

count_triplets

// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	srand(chrono::steady_clock::now().time_since_epoch().count());
	cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}





const int N = 1e5+5;
const int M = 2e5+5;

int n, m;
pii edg[M];
V<int> adj[N];

int sz[N];
struct Dsu{
	int p[N];
	Dsu(){
		reset();
	}
	void reset(){
		rep(i,0,n+1) p[i]=i, sz[i]=1;
	}
	int find(int x){
		return p[x]==x ? x : p[x]=find(p[x]);
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	void unite(int x,int y){
		if((x=find(x))==(y=find(y))) return;
		p[y] = x;
		sz[x] += sz[y];
	}
} dsu;

bool bg[M];
int t[N], up[N], tim=0;
void dfs_bridge(int x=1,int par=-1){
	up[x] = t[x] = ++tim;

	for(int e : adj[x]){
		int y = edg[e].ff^edg[e].ss^x;
		if(y==par) continue;

		if(t[y]==-1){
			dfs_bridge(y, x);
		}
		up[x] = min(up[x],up[y]);

		if(up[y] > t[x]){
			bg[e] = 1;
			// cout << x _ y << nl;

			dsu.reset();
			rep(i,1,m+1) if(i!=e){
				dsu.unite(edg[i].ff, edg[i].ss);
			}
			assert(!dsu.same(x,y));
			// cout << x _ y << nl;
		}
		else{
			dsu.reset();
			rep(i,1,m+1) if(i!=e){
				dsu.unite(edg[i].ff, edg[i].ss);
			}
			assert(dsu.same(x,y));
			// cout << x _ y << nl;
		}
	}
}



V<int> cadj[N];
int ans = 0;

bool vis[N];
int tot;
void dfs_tot(int x,int par=-1){
	tot += sz[x];
	for(int y : cadj[x]) if(y!=par){
		dfs_tot(y, x);
	}
}
void dfs_dp(int x,int par=-1){
	vis[x] = 1;
	int orisz = sz[x];
	for(int y : cadj[x]) if(y!=par){
		dfs_dp(y, x);
		sz[x] += sz[y];
	}

	// dbg(x);
	// dbg(orisz); dbg(sz[x]);

	// S,C,T in this component
	ans += orisz *(orisz-1) *(orisz-2);
	// dbg(orisz *(orisz-1) *(orisz-2));

	// S,C in this component
	// C,T in this component
	ans += 2 *(orisz-1) *(orisz-1) *(tot-orisz);
	// dbg(2 *(orisz-1) *(orisz-1) *(tot-orisz));


	// C is LCA
	// C in this component, S from a child, T from other child
	for(int y : cadj[x]) if(y!=par){
		ans += orisz *sz[y] *(sz[x]-orisz-sz[y]);
		// dbg(orisz *sz[y] *(sz[x]-1-sz[y]));
	}

	// C is not LCA
	// C in this component, S from a child, T from parent
	// C in this component, T from a child, C from parent
	ans += 2 *orisz *(sz[x]-orisz) *(tot-sz[x]);
	// dbg(2 *orisz *(sz[x]-orisz) *(tot-sz[x]));

	// dbg(ans);
	// cout << nl;
}

void solve(){
	
	cin >> n >> m;
	
	rep(e,1,m+1){
		int u, v;
		cin >> u >> v;

		edg[e] = {u,v};
		adj[u].push_back(e);
		adj[v].push_back(e);
	}
	

	rep(i,1,n+1) t[i] = -1;
	rep(i,1,n+1) if(t[i]==-1){
		dfs_bridge(i);
	}

	dsu.reset();
	rep(e,1,m+1) if(!bg[e]){
		auto[x,y] = edg[e];
		// cout << "UNITE" _ x _ y << nl;
		dsu.unite(x,y);
	}
	rep(e,1,m+1) if(bg[e]){
		auto[x,y] = edg[e];
		x = dsu.find(x);
		y = dsu.find(y);

		cadj[x].push_back(y);
		cadj[y].push_back(x);
	}

	rep(i,1,n+1)
	// for(int i=n; i>=1; i--)
	if(i==dsu.find(i) && !vis[i]){
		// dbg(i);
		tot = 0;
		dfs_tot(dsu.find(i));
		// dbg(tot);
		dfs_dp(dsu.find(i));
		// dbg(ans);

		// cout << nl << nl;
	}

	cout << ans << nl;
}

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