Submission #733204

#	Time	Username	Problem	Language	Result	Execution time	Memory
733204		sentheta	Duathlon (APIO18_duathlon)	C++17	31 / 100	125 ms	30984 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 = 2e5+5;

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

bool vis[N];

V<int> cadj[N], stak;
int id;

bool art[N];
int t[N], up[N], tim=0;
void dfs_art(int x,int par){
	up[x] = t[x] = ++tim;
	stak.push_back(x);
		
	int children = 0;
	for(int y : adj[x]) if(y!=par){
		if(!t[y]){
			children++;
			dfs_art(y, x);
		
			// new bcc
			if(up[y] >= t[x]){
				cadj[x].push_back(++id);
				cadj[id].push_back(x);
				// dbg(x); dbg(id); dbg(y);
				while(stak.back()!=x){
					cadj[stak.back()].push_back(id);
					cadj[id].push_back(stak.back());
					stak.pop_back();
				}
			}
		}

		up[x] = min(up[x], up[y]);
		if(par!=-1) art[x] = up[y]>=t[x];
	}
	if(par==-1) art[x] = children>=2;
}


int sz[N];
void dfs_sz(int x,int par){
	vis[x] = 1;
	for(int y : cadj[x]) if(y!=par){
		dfs_sz(y, x);
		sz[x] += sz[y];
	}
}

int ans = 0;
void reroot(int x,int par){
	vis[x] = 1;
	if(x > n){
		// dbg(x);
		int sum = 0;
		for(int y : cadj[x]){
			// dbg(y); dbg(sz[y]);
			sum += sz[y]*(sz[y]-1);
		}
		for(int y : cadj[x]){
			ans -= sum -sz[y]*(sz[y]-1);
		}
		// dbg(ans);
		// cout << nl;
	}

	int orisz = sz[x];
	for(int y : cadj[x]) if(y!=par){
		sz[x] = orisz - sz[y];
		sz[y] += sz[x];

		reroot(y, x);
	}
}

void solve(){
	
	cin >> n >> m;

	rep(i,0,m){
		int u, v; cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	id = n;
	rep(x,1,n+1) if(!t[x]){
		dfs_art(x, -1);
	}

	// cout << "ART[] ";
	// rep(x,1,n+1) if(art[x]) cout << x << " ";
	// cout << endl << endl;

	// cout << "BCC" << nl;
	// rep(x,1,n+1) for(int y : cadj[x]){
	// 	cout << x _ y << nl;
	// }
	// cout << endl;

	// return;

	rep(x,1,n+1){
		vis[x] = 0;
		sz[x] = 1;
	}
	rep(x,1,n+1) if(!vis[x]){
		dfs_sz(x, -1);
		ans += sz[x] *(sz[x]-1) *(sz[x]-2);
	}
	// dbg(ans);


	rep(x,1,id+1){
		vis[x] = 0;
	}
	rep(x,1,id+1) if(!vis[x]){
		reroot(x, -1);
	}

	cout << ans << nl;

}

• 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