oj.uz

Submission #1059088

# Submission time Handle Problem Language Result Execution time Memory
1059088 2024-08-14T16:58:14 Z vjudge1 Cyberland (APIO23_cyberland) C++17
44 / 100
 25 ms 8028 KB 
#include "cyberland.h"
#include <queue>
#include <cstdint>
// #include <iostream>
using namespace std;

double solve(int N, int M, int K, int H, vector <int> x, vector <int> y, vector <int> c, vector <int> arr) {
	vector <pair <int, int>> graph[N];
	for (int i = 0; i < M; i++) {
		graph[x[i]].emplace_back(y[i], c[i]);
		graph[y[i]].emplace_back(x[i], c[i]);
	}
	queue <int> bfs;
	bool vis[N] = {};
	bfs.push(0);
	vis[0] = vis[H] = true;
	arr[0] = 0;
	while (!bfs.empty()) {
		int u = bfs.front();
		bfs.pop();
		for (auto &[v, w] : graph[u]) {
			if (vis[v]) continue;
			vis[v] = true;
			bfs.push(v);
		}
	}
	int64_t path[N];
	for (int i = 0; i < N; i++) {
		if (!vis[i]) arr[i] = 1;
		vis[i] = false;
		path[i] = 1e17;
	}
	/* for (int i = 0; i < N; i++) cerr << arr[i] << ' ';
	cerr << endl; */
	priority_queue <pair <int64_t, int>> q;
	q.emplace(0, H);
	path[H] = 0;
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		if (!arr[u]) return path[u];
		for (auto &[v, w] : graph[u]) {
			if (!vis[v] && path[v] > path[u] + w) {
				path[v] = path[u] + w;
				q.emplace(-path[v], v);
			}
		}
	}
	return -1;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 600 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 604 KB Correct.
2 Correct 13 ms 596 KB Correct.
3 Correct 13 ms 348 KB Correct.
4 Correct 13 ms 348 KB Correct.
5 Correct 13 ms 560 KB Correct.
6 Correct 10 ms 1256 KB Correct.
7 Correct 14 ms 1372 KB Correct.
8 Correct 7 ms 2396 KB Correct.
9 Correct 13 ms 600 KB Correct.
10 Correct 12 ms 484 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 348 KB Correct.
2 Correct 15 ms 1452 KB Correct.
3 Correct 12 ms 1372 KB Correct.
4 Correct 13 ms 1252 KB Correct.
5 Correct 13 ms 1372 KB Correct.
6 Correct 3 ms 1224 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 5980 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 604 KB Correct.
2 Correct 15 ms 1628 KB Correct.
3 Correct 14 ms 1372 KB Correct.
4 Correct 14 ms 2396 KB Correct.
5 Correct 12 ms 1116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 348 KB Correct.
2 Correct 12 ms 604 KB Correct.
3 Correct 25 ms 8028 KB Correct.
4 Correct 8 ms 1172 KB Correct.
5 Correct 13 ms 348 KB Correct.
6 Correct 13 ms 1372 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 348 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 348 KB Wrong Answer.
2 Halted 0 ms 0 KB -