oj.uz

Submission #59293

# Submission time Handle Problem Language Result Execution time Memory
59293 2018-07-21T12:14:52 Z thiago4532 Duathlon (APIO18_duathlon) C++17
0 / 100
 4 ms 864 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 732 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 3 ms 732 KB Output is correct
5 Correct 3 ms 732 KB Output is correct
6 Correct 1 ms 732 KB Output is correct
7 Correct 4 ms 732 KB Output is correct
8 Incorrect 3 ms 732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 732 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 3 ms 732 KB Output is correct
5 Correct 3 ms 732 KB Output is correct
6 Correct 1 ms 732 KB Output is correct
7 Correct 4 ms 732 KB Output is correct
8 Incorrect 3 ms 732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 732 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 3 ms 732 KB Output is correct
5 Correct 3 ms 732 KB Output is correct
6 Correct 1 ms 732 KB Output is correct
7 Correct 4 ms 732 KB Output is correct
8 Incorrect 3 ms 732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 732 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 3 ms 732 KB Output is correct
5 Correct 3 ms 732 KB Output is correct
6 Correct 1 ms 732 KB Output is correct
7 Correct 4 ms 732 KB Output is correct
8 Incorrect 3 ms 732 KB Output isn't correct
9 Halted 0 ms 0 KB -