Submission #1086016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086016		peacebringer1667	Duathlon (APIO18_duathlon)	C++17	5 / 100	981 ms	1048576 KiB

count_triplets

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e5 + 5;

vector<vector<int>> vec(maxn);
void input(int n,int m){
	while (m--){
		int u,v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
}

namespace sub1{
	bool check(int n,int m){
		return (n <= 10 && m <= 100);
	}
	const int N = 15;
	
	bool E[N][N],path[N][N][N];
	
	void gen_edge(int n){
		for (int u = 1 ; u <= n ; u++)
		  for (int v : vec[u])
		    E[u][v] = E[v][u] = 1;
	}
	
	void checker(int mask,int n){
		vector <int> node;
		
		for (int u = 1 ; u <= n ; u++)
		  if (1 << (u - 1) & mask)
		    node.push_back(u); 
		
		do{
		   bool kt = 1;
           for (int i = 1 ; i < node.size() ; i++)
             if (!E[node[i]][node[i - 1]]){
             	kt = 0;
             	break;
			 }
			
		    if (kt)
		    	for (int u : node)
		    	  path[node[0]][u][node.back()] = 1;
		}while (next_permutation(node.begin(),node.end()));
	}
	
	void solve(int n,int m){
		gen_edge(n);
		int lim_mask = (1 << n);
		
		for (int mask = 1 ; mask < lim_mask ; mask++)
		  if (__builtin_popcount(mask) >= 3)
		    checker(mask,n);
		
		int res = 0;
		for (int u = 1 ; u <= n ; u++)
		  for (int v = 1 ; v <= n ; v++)
		    for (int k = 1 ; k <= n ; k++)
		      if (u != v && v != k && u != k)
		        res += path[u][v][k];
		
		cout << res;
	}
}

ll res = 0;
int sz[maxn];

ll dfs(int u,int par,int n){
	sz[u] = 1;
	ll res = 0;
	
	for (int v : vec[u])
	  if (v != par){
	  	res += dfs(v,u,n);
	  	sz[u] += sz[v];
	  }
	
	ll cur1 = 0,cur2 = 0;
	
	for (int v : vec[u])
	  if (v != par){
	  	res += cur2 * (ll)sz[v];
	  	
	  	cur2 += cur1 * (ll)sz[v]; 
	  	cur1 += sz[v];
	  }
	
	res -= cur2 * (ll)(n - sz[u]);
	
	return res;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,m;
	cin >> n >> m;
	input(n,m);
	
	if (sub1::check(n,m)){
		sub1::solve(n,m);
		return 0;
	}
	
	res = (ll)n*(ll)(n - 1)*(ll)(n - 2)/6;
	res -= dfs(1,0,n);
	
	res *= 2;
	
	cout << res;

	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void sub1::checker(int, int)':
count_triplets.cpp:45:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |            for (int i = 1 ; i < node.size() ; i++)
      |                             ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 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