Submission #387951

#	Time	Username	Problem	Language	Result	Execution time	Memory
387951		NurstanDuisengaliev	Duathlon (APIO18_duathlon)	C++14	0 / 100	64 ms	12804 KiB

count_triplets

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define int ll

using namespace std;

const int N = (int)1e5 + 123;
int n, m;
vector <int> g[N];  
int used[N];
ll ans = 0, LEN = 0;
bool FindC (int v) {
 	used[v] = 1;
 	bool yes = 0;
 	LEN ++;
 	for (auto to : g[v]) {
 		if (!used[to]) {
 			yes |= FindC (to);
 		}
 		else if (used[to] == 1) {
 			yes = 1;						
 		}
 	}
 	used[v] = 2;
 	return yes;
}
main () {
    ios_base::sync_with_stdio (0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
    	int u, v;
    	cin >> u >> v;
    	g[u].pb (v);
    	g[v].pb (u);
    }
  	int maxisz = 0;
  	for (int i = 1; i <= n; i ++) {
  		maxisz = max (maxisz, sz (g[i]));
  	}
  	if (maxisz <= 2) {
  		for (int i = 1; i <= n; i ++) {
  			if (!used[i]) {
  				LEN = 0;
  				if (FindC (i)) {
  				    ans += ((LEN * 1ll * (LEN - 1) * 1ll * (LEN - 2)) / 3); 
  				}
  				else {
  					for (int j = 1; j <= LEN - 2; j ++) {
  						ans += (LEN - (j + 2) + 1) * 1ll * j;
  					}	
  				}
  			}	
  		}	
  		cout << ans;
  		exit (0);
  	}
  	
	return 0;
}

Compilation message (stderr)

count_triplets.cpp:30:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main () {
      |       ^

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