Submission #1196480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196480		mertbbm	Duathlon (APIO18_duathlon)	C++20	100 / 100	98 ms	31168 KiB

count_triplets

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

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<ld,ld>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
int ran(int index){return rng()%index;}

vector<int>adj[200005];
vector<int>bcc[200005];
int in[200005];
int dp[200005];
int n,m;
int ptr=1;
int cnt=1;
vector<int>stk;
int num=0;

void dfs(int index, int par){
	in[index]=dp[index]=ptr++;
	stk.push_back(index);
	num++;
	for(auto it:adj[index]){
		if(it==par) continue;
		if(in[it]){
			dp[index]=min(dp[index],in[it]);
		}
		else{
			dfs(it,index);
			dp[index]=min(dp[index],dp[it]);
			if(dp[it]>=in[index]){
				bcc[index].push_back(n+cnt);
				while(!bcc[n+cnt].size()||bcc[n+cnt].back()!=it){
					bcc[n+cnt].push_back(stk.back());
					stk.pop_back();
				}
				cnt++;
			}
		}
	}
}

int counter=0;
int sz[200005];

void dfs2(int index){
	sz[index]=(index<=n);
	for(auto it:bcc[index]){
		dfs2(it);
		sz[index]+=sz[it];
		if(index>n){
			counter-=bcc[index].size()*sz[it]*(sz[it]-1);
		}
	}
	if(index>n) counter-=bcc[index].size()*(num-sz[index])*(num-sz[index]-1);
}

void solve(){
	cin >> n >> m;
	
	int temp,temp2;
	for(int x=0;x<m;x++){
		cin >> temp >> temp2;
		adj[temp].push_back(temp2);
		adj[temp2].push_back(temp);
	}
	
	for(int x=1;x<=n;x++){
		if(in[x]) continue;
		num=0;
		dfs(x,-1);
		dfs2(x);
		counter+=(num)*(num-1)*(num-2);
	}
	
	cout << counter;
}	
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

• 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