Submission #48872

#	Time	Username	Problem	Language	Result	Execution time	Memory
48872		IvanC	Duathlon (APIO18_duathlon)	C++17	31 / 100	263 ms	22888 KiB

count_triplets

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

typedef long long ll;
typedef pair<int,int> ii;

const int MAXN = 1e5 + 10;


vector<int> grafo[MAXN],arvore[MAXN];
int N,M,e1[2*MAXN],e2[2*MAXN],isbridge[2*MAXN],num[MAXN],low[MAXN],dfsCount,treeComp,bridgeTreeId[MAXN],bridge_sz[MAXN],sz[MAXN],block[MAXN];
ll tot,comp_size;

void dfs_tarjan(int v,int p){
	num[v] = low[v] = ++dfsCount;
	for(int i = 0;i<grafo[v].size();i++){
		int idx = grafo[v][i];
		int u = (e1[idx] != v) ? e1[idx] : e2[idx];
		if(u == p) continue;
		if(num[u] == 0){
			dfs_tarjan(u,v);
			if(low[u] > num[v]) isbridge[idx] = 1;
			low[v] = min(low[v],low[u]);
		}
		else{
			low[v] = min(low[v],num[u]);
		}
	}
}
void dfs_bridge(int v,int p,int compId){
	if(compId == -1) compId = ++treeComp;
	bridgeTreeId[v] = compId;
	for(int i = 0;i<grafo[v].size();i++){
		int idx = grafo[v][i];
		int u = (e1[idx] != v) ? e1[idx] : e2[idx];
		if(u == p || bridgeTreeId[u]) continue;
		if(isbridge[idx]){
			dfs_bridge(u,v,-1);
			arvore[bridgeTreeId[v]].push_back(bridgeTreeId[u]);
			arvore[bridgeTreeId[u]].push_back(bridgeTreeId[v]);
		}
		else{
			dfs_bridge(u,v,compId);
		}
	}
}

void dfs_tree_1(int v,int p){
	block[v] = 1;
	sz[v] = bridge_sz[v];
	for(int u : arvore[v]){
		if(u == p) continue;
		dfs_tree_1(u,v);
		sz[v] += sz[u];
	}
}

void dfs_tree_2(int v,int p){
	tot += 1LL*(bridge_sz[v])*max(bridge_sz[v] - 1,0)*max(bridge_sz[v]-2,0);
	vector<int> filhos;
	for(int u : arvore[v]){
		if(u == p) continue;
		filhos.push_back(sz[u]);
		dfs_tree_2(u,v);
	}
	filhos.push_back(comp_size - sz[v]);
	for(int i = 0;i<filhos.size();i++){
		int sub_arvore = filhos[i];
		tot += 1LL*bridge_sz[v]*sub_arvore*(comp_size - sub_arvore - bridge_sz[v]);
		tot += 2LL*sub_arvore*(bridge_sz[v] - 1)*max(bridge_sz[v] - 2,0);
		tot += 2LL*sub_arvore*(bridge_sz[v] - 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){
			dfs_tarjan(i,-1);
			dfs_bridge(i,-1,-1);
		}
	}

	for(int i = 1;i<=N;i++) bridge_sz[bridgeTreeId[i]]++;

	for(int i = 1;i<=treeComp;i++){
		if(block[i]) continue;
		dfs_tree_1(i,-1);
		comp_size = sz[i];
		dfs_tree_2(i,-1);
	}

	printf("%lld\n",tot);

	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs_tarjan(int, int)':
count_triplets.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<grafo[v].size();i++){
                ~^~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs_bridge(int, int, int)':
count_triplets.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<grafo[v].size();i++){
                ~^~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs_tree_2(int, int)':
count_triplets.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<filhos.size();i++){
                ~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:76: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:79: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: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10