Submission #982491

#	Time	Username	Problem	Language	Result	Execution time	Memory
982491		MuhammadSaram	Duathlon (APIO18_duathlon)	C++17	31 / 100	51 ms	16836 KiB

count_triplets

/********************* بسم الله الرحمن الرحيم ***********************/
 /******************** ٱلْحَمْدُ لِلَّٰهِ رَبِّ ٱلْعَالَمِينَ *************************/
/******************* Prophet Muhammad صلى الله عليه وسلم ************/
   /*********************** وَقُل رَّبِّ زِدْنِي عِلْمًا **************************/

#ifdef ONLINE_JUDGE
	#pragma GCC optimize("Ofast")
	#pragma GCC optimize("O3,unroll-loops")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#else

#endif

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

#define int long long
#define endl '\n'
#define in binary_search
#define ll long long
#define ld long double
#define Hey ios::sync_with_stdio(false);
#define Welcome cin.tie(NULL), cout.tie(NULL);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()

const int M = 1e5 + 1;

vector<int> nei[M];
bool vis[M];
int cnt,ans,subt[M],deg[M],dep[M];
vector<int> cc;

void dfs(int u)
{
	vis[u]=true;
	subt[u]=1;
	cnt++;
	cc.push_back(u);
	for (int i:nei[u])
		if (!vis[i])
		{
			dfs(i);
			subt[u]+=subt[i];
		}
}

void dfs1(int u)
{
	vis[u]=true;
	for (int i:nei[u])
		if (!vis[i])
		{
			ans+=(subt[i]-1)*(cnt-subt[i]-1)*2;
			ans+=cnt-2;
			dep[i]=dep[u]+1;
			dfs1(i);
		}
		else if(dep[i]<dep[u] and dep[u]-1!=dep[i])
		{
			int cyc=dep[u]-dep[i]+1;
			int x=cnt-subt[i];
			ans+=cyc*(cyc-2)*(cyc-1)/3*2;
			ans+=x*(cyc-1)*(cyc-2);
			ans+=(subt[u]-1)*(cyc-1)*(cyc-2);
		}
}

void solve()
{
	int n,m;
	cin>>n>>m;
	for (int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		nei[u].push_back(v);
		nei[v].push_back(u);
		deg[u]++;
		deg[v]++;
	}
	for (int i=1;i<=n;i++)
	{
		if (!vis[i])
		{
			cc.clear();
			cnt=0;
			dfs(i);
			for (int j:cc)
				vis[j]=false;
			dfs1(i);
		}
	}
	cout<<ans<<endl;
}

signed main()
{
	Hey! Welcome // S'up
	
	int t = 1;
	cout<<fixed<<setprecision(20);
	while (t--)
		solve();
	
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:99:5: warning: value computed is not used [-Wunused-value]
   99 |  Hey! Welcome // S'up
      |     ^

• 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