Submission #138789

#	Time	Username	Problem	Language	Result	Execution time	Memory
138789		FedericoS	Duathlon (APIO18_duathlon)	C++14	0 / 100	1119 ms	1048580 KiB

count_triplets

#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

bool sub3=true;

ll N,M;
ll x,y;
ll A,B,ans;
bool V[300005];
vector<ll> grafo[300005];
ll S[300005];

map <pll,ll> E;

void DFSsub3(int k){

	B++;
	if(V[k])
		return;
	A++;
	V[k]=true;

	for(int f:grafo[k])
		DFSsub3(f);}

void DFS(int k, int p=-1){

	for(int f:grafo[k])
		if(f!=p)
			DFS(f,k);

	E[{p,k}]=1;

	for(int f:grafo[k])
		if(f!=p)
			E[{p,k}]+=E[{k,f}];

	E[{k,p}]=N-E[{p,k}];

}

int main(){

	cin>>N>>M;
	for(int i=0;i<M;i++){
		cin>>x>>y;
		grafo[x].push_back(y);
		grafo[y].push_back(x);
	}

	for(int i=1;i<N+1;i++)
		if(grafo[i].size()>2)
			sub3=false;

	sub3=false;

	if(sub3){
		for(int i=1;i<N+1;i++)
			if(!V[i]){
				A=B=0;
				DFSsub3(i);
				if(B-1==2*A)
					ans+=(A*(A-1)*(A-2));
				else	
					ans+=(A*(A-1)*(A-2))/3;
			}
		cout<<ans;}
	else{
		for(int i=1;i<N+1;i++)
			DFS(i);

		for(ll i=1;i<N+1;i++){
			A=B=0;
			for(ll f:grafo[i]){
				A+=E[{i,f}];
				B+=E[{i,f}]*E[{i,f}];
			}
			A=A*A;
			ans+=A-B;
		}

		cout<<ans;

	}

}

• 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