제출 #59293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59293		thiago4532	Duathlon (APIO18_duathlon)	C++17	0 / 100	4 ms	864 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;
const int maxn = 20, inf = 0x3f3f3f3f;
vector<int> grafo[maxn];
int dist[maxn];
bool mark[maxn];

void bfs(int u, int l){
	memset(dist, inf, sizeof dist);
	dist[u] = 0;
	dist[l] = -inf;

	queue<int> fila;
	fila.push(u);

	while(!fila.empty()){
		int u = fila.front();
		fila.pop();

		for(auto v : grafo[u]){
			if(!mark[v] && dist[v] > dist[u] + 1){
				dist[v] = dist[u] + 1;
				fila.push(v);
			}
		}
	}
}

void dfs(int u){
	mark[u] = true;

	int val = -1;
	for(auto v : grafo[u]){
		if(dist[v] + 1 == dist[u]){
			if(val == -1) val = v;
			else val = -2;
		}
	}

	if(val > 0) dfs(val);
	else return;
}

int main(){
	int n, m;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int a, b;
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
	}


	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				if(i == j || j == k || i == k) continue;
				memset(mark, 0, sizeof mark);
				
				bfs(i, k);
				if(dist[j] >= inf) continue;
				dfs(j);
				bfs(j, 0);
				if(dist[k] < inf) ans++;
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

• 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