Submission #59336

#	Time	Username	Problem	Language	Result	Execution time	Memory
59336		IvanC	Duathlon (APIO18_duathlon)	C++17	66 / 100	406 ms	36420 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MAXN = 2*1e5 + 10;
 
vector<int> grafo[MAXN],tree[MAXN],meucomponente[MAXN];
int e1[MAXN],e2[MAXN],e3[MAXN],jafoi[MAXN],N,M;
int compSz[MAXN],subtreeSz[MAXN],compId[MAXN],lastComp;
int low[MAXN],num[MAXN],dfsCount,total_componente;
ll trincas_total;
 
void dfs1(int v,int aresta){
	total_componente++;
	num[v] = low[v] = ++dfsCount;
	for(int i : grafo[v]){
		if(i == aresta) continue;
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(num[u] == 0){
			dfs1(u,i);
			if(num[v] < low[u]){
				e3[i] = 1;
			}
			low[v] = min(low[v],low[u]);
		}
		else{
			low[v] = min(low[v],num[u]);
		}
	}
}
 
void dfs2(int v,int aresta){
	if(jafoi[v]) return;
	jafoi[v] = 1;
	compSz[compId[v]]++;
	meucomponente[compId[v]].push_back(v);
	for(int i : grafo[v]){
		if(i == aresta) continue;
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(num[v] >= num[u] ) continue;
		if(e3[i] == 1){
			lastComp++;
			compId[u] = lastComp;
			tree[compId[v]].push_back(compId[u]);
			tree[compId[u]].push_back(compId[v]);
			dfs2(u,i);
		}
		else{
			compId[u] = compId[v];
			dfs2(u,i);
		}
	}
}
 
void dfs3(int v,int p){
	subtreeSz[v] = compSz[v];
	for(int u : tree[v]){
		if(u == p) continue;
		dfs3(u,v);
		subtreeSz[v] += subtreeSz[u];
	}
	for(int u : tree[v]){
		if(u == p) continue;
		int v1 = compSz[v]; // dentro
		int v2 = subtreeSz[u]; // fora, esta subtree
		int v3 = total_componente - v1 - v2; // fora, outras subtrees
		trincas_total += 1LL*v1*v2*v3; // fora-dentro-fora
		trincas_total += 2LL*v2*(v1 - 1)*(v1 - 1); // fora-dentro-dentro
	}
	int v1 = compSz[v]; // dentro
	int v2 = (total_componente - subtreeSz[v]); // fora, esta subtree
	int v3 = (subtreeSz[v] - compSz[v]);// fora, outras subtrees
	trincas_total += 1LL*v1*v2*v3; // fora-dentro-fora
	trincas_total += 2LL*v2*(v1 - 1)*(v1 - 1); // fora-dentro-dentro
	trincas_total += 1LL*(v1)*(v1 - 1)*(v1 - 2); // dentro-dentro-dentro
	
	for(int k : meucomponente[v]){
		
		vector<int> tamanhos;
		int filhos = 0;
		
		for(int i : grafo[k]){
			int u = (e1[i] != k) ? (e1[i]) : (e2[i]);
			int l = compId[u];
			if(l == v) continue;
			if(l == p){
				tamanhos.push_back(total_componente - subtreeSz[v]);
			}
			else{
				tamanhos.push_back(subtreeSz[l]);
			}
		}
		
		for(int valor : tamanhos) filhos += valor;
		
		for(int valor : tamanhos){
			trincas_total -= 1LL*(valor)*(filhos - valor)*(v1 - 1);
		}
		
	}
	
}
 
int main(){
	
	scanf("%d %d",&N,&M);
	for(int i = 1;i<=M;i++){
		scanf("%d %d",&e1[i],&e2[i]);
		grafo[e1[i]].push_back(i);
		grafo[e2[i]].push_back(i);
	}
	
	for(int i = 1;i<=N;i++){
		if(num[i] != 0) continue;
		total_componente = 0;
		dfs1(i,-1);
		lastComp++;
		compId[i] = lastComp;
		dfs2(i,-1);
		dfs3(compId[i],-1);
	}
	
	printf("%lld\n",trincas_total);
	
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&e1[i],&e2[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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