Submission #1192039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192039		tinkerbells	철인 이종 경기 (APIO18_duathlon)	C++20	31 / 100	46 ms	19612 KiB

count_triplets

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
typedef long long LL;
typedef long double LD;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;

const int MAXN=1e5+5;
vector<int> adj[MAXN];
LL siz[MAXN];
LL ans=0;

bool chk[MAXN]; //check if u is in stack or not
stack<LL> st;
LL low[MAXN]; //lowest id node reachable from u
LL num[MAXN]; //dfs order of u
LL cnt=0; //count for dfs order#
LL sccid=0; //id for scc
LL scc[MAXN];
LL sccsize[MAXN];

void dfs(LL u, LL par){
	cnt++;
	low[u]=cnt;
	num[u]=cnt;
	st.push(u);
	for (auto to: adj[u]){
		if (to==par) continue;
		if (chk[to]==false){
			if (num[to]==0){
				dfs(to, u);
				low[u]=min(low[u], low[to]);
			}
			else low[u]=min(low[u], num[to]);
		} 
	}
	if (low[u]==num[u]){
		sccid++;
		while(1){
			auto p=st.top();
			st.pop();
			sccsize[sccid]++;
			scc[p]=sccid;
			chk[p]=true;
			if (p==u) break;
		}
	}
}

void dfs2(int u, int par){
	siz[u]=sccsize[u];
	for (auto to: adj[u]){
		if (to==par) continue;
		dfs2(to,u);
		siz[u]+=siz[to];
	}
}

void cal(int u, int par, LL total){
	LL calc=(total-sccsize[u])*(total-sccsize[u]);
	for (auto to: adj[u]){
		if (to==par){
			calc-=(total-siz[u])*(total-siz[u]);
		}
		else{
			calc-=(siz[to])*(siz[to]);
			cal(to, u, total);
		}
	}
	ans+=calc*sccsize[u];
	if (sccsize[u]>=3) ans+=2*(sccsize[u]-1)*(sccsize[u]-1)*(total-sccsize[u]);
}

const LL MAXM=2e5+5;
LL u[MAXM];
LL v[MAXM];

signed main(){
	FAST;
	int n,m; cin>>n>>m;
	FOR(i,m){
		int a,b; cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		
		u[i]=a;
		v[i]=b;
	}
	
	FR(i,1,n+1){
		if (num[i]==0) dfs(i,-1);
	}

	FR(i,1,n+1) adj[i].clear();
	FOR(i,m){
		if (scc[u[i]]!=scc[v[i]]){
			int a=scc[u[i]], b=scc[v[i]];
			adj[a].push_back(b);
		    adj[b].push_back(a);
		}
	}
	
	FR(i,1,sccid+1){
		if (siz[i]==0){
			dfs2(i,-1);
			cal(i,-1,siz[i]);
		}
	}
	
	FR(i,1,sccid+1){
		if (sccsize[i]>=3){
			LL x=sccsize[i];
			ans+=x*(x-1)*(x-2);
		}
	}
	
	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