oj.uz

Submission #991514

# Submission time Handle Problem Language Result Execution time Memory
991514 2024-06-02T10:56:58 Z Muaath_5 Train (APIO24_train) C++17
5 / 100
 60 ms 16792 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5+5;
const ll INF = 5e15;

vector<array<int, 4>> adj[N];
ll dist[N];

long long solve(int n, int m, int w, std::vector<int> T,
	std::vector<int> X, std::vector<int> Y,
	std::vector<int> A, std::vector<int> B, std::vector<int> C,
	std::vector<int> L, std::vector<int> R) {
	
	
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i = 0; i < m; i++)
		adj[X[i]].push_back({A[i], B[i], Y[i], C[i]});
	for (int i = 0; i < n; i++)
		sort(adj[i].begin(), adj[i].end());
	
	dist[0] = 0;
	for (int i = 1; i < n; i++) dist[i] = INF;
	
	priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
	pq.push({0, 0, 0});
	while (pq.size()) {
		auto [cost, tim, node] = pq.top();
		pq.pop();
		if (cost > dist[node]) continue;
		dist[node] = cost;
		for (auto [l, r, y, c] : adj[node]) {
			if (l >= tim && cost+c < dist[y])
				pq.push({cost+c, r, y});
		}
	}
	return (dist[n-1] == INF ? -1 : dist[n-1]);
}

#ifdef MUAATH_5
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cout << solve(3, 3, 0, {20, 30, 40}, {0, 1, 0}, {1, 2, 2}, {1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19}) << '\n';
	cout << solve(3, 5, 6, {30, 38, 33}, {0, 1, 0, 0, 1}, {2, 0, 1, 2, 2}, {12, 48, 26, 6, 49}, {16, 50, 28, 7, 54}, {38, 6, 23, 94, 50}, {32, 14, 42, 37, 2, 4}, {36, 14, 45, 40, 5, 5}) << '\n';
	int _;
	cin >> _;
	while (_--) {
		int n, m, w;
		cin >> n >> m >> w;
		vector<int> t(n), x(m), y(m), a(m), b(m), c(m), l(w), r(w);
		for (int &i : t)
			cin >> i;
		for (int i = 0; i < m; i++) {
			cin >> x[i] >> y[i] >> a[i] >> b[i] >> c[i];
		}
		for (int i = 0; i < w; i++) {
			cin >> l[i] >> r[i];
		}
		cout << solve(n, m, w, t, x, y, a, b, c, l, r) << '\n';
	}
}
#endif

Subtask #1
0.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 13304 KB Correct.
2 Correct 50 ms 14160 KB Correct.
3 Correct 1 ms 6492 KB Correct.
4 Correct 9 ms 7260 KB Correct.
5 Correct 2 ms 6744 KB Correct.
6 Correct 42 ms 13820 KB Correct.
7 Correct 2 ms 6492 KB Correct.
8 Correct 48 ms 16792 KB Correct.
9 Correct 60 ms 14244 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 13304 KB Correct.
2 Correct 50 ms 14160 KB Correct.
3 Correct 1 ms 6492 KB Correct.
4 Correct 9 ms 7260 KB Correct.
5 Correct 2 ms 6744 KB Correct.
6 Correct 42 ms 13820 KB Correct.
7 Correct 2 ms 6492 KB Correct.
8 Correct 48 ms 16792 KB Correct.
9 Correct 60 ms 14244 KB Correct.
10 Incorrect 59 ms 15184 KB Wrong Answer.
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

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