oj.uz

Submission #971665

# Submission time Handle Problem Language Result Execution time Memory
971665 2024-04-29T07:07:19 Z Nomio Cyberland (APIO23_cyberland) C++17
15 / 100
 25 ms 7248 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
	vector<pair<int, int>> v[n];
	for(int i = 0; i < m; i++) {
		v[x[i]].push_back({y[i], c[i]});
		v[y[i]].push_back({x[i], c[i]});
	}
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	vector<ll> dis(n, 1e18);
	dis[0] = 0;
	pq.push({0, 0});
	while(!pq.empty()) {
		ll x = pq.top().first;
		int y = pq.top().second;
		pq.pop();
		if(dis[y] != x) continue;
		for(pair<int, int> p : v[y]) {
			int X = p.first;
			int Y = p.second;
			if(a[X] == 0 && dis[X] != 0) {
				dis[X] = 0;
				pq.push({0, X});	
			} else if(dis[X] > dis[y] + Y) {
				dis[X] = dis[y] + Y;
				pq.push({dis[X], X});
			}
		}
	}
	if(dis[h] == 1e18) {
		return -1;
	}
	queue<int> q;
	q.push(h);
	bool vis[n] {};
	vis[0] = vis[h] = 1;
	ll S = dis[h];
	while(!q.empty()) {
		int X = q.front();
		q.pop();
		if(a[X] == 0) S = min(S, dis[X]);
		for(pair<int, int> p : v[X]) {
			if(!vis[p.first]) {
				vis[p.first] = 1;
				q.push(X);
			}
		}
	}
	return S;
}
//
//int main() {
//	cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << '\n';
//}

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1368 KB Correct.
2 Correct 25 ms 1620 KB Correct.
3 Correct 21 ms 1576 KB Correct.
4 Correct 22 ms 1372 KB Correct.
5 Correct 22 ms 1624 KB Correct.
6 Correct 19 ms 2144 KB Correct.
7 Correct 24 ms 2384 KB Correct.
8 Correct 10 ms 2908 KB Correct.
9 Correct 20 ms 1384 KB Correct.
10 Correct 22 ms 1372 KB Correct.

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1372 KB Correct.
2 Correct 21 ms 1488 KB Correct.
3 Correct 21 ms 1368 KB Correct.
4 Correct 19 ms 2392 KB Correct.
5 Correct 17 ms 1112 KB Correct.

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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