oj.uz

Submission #864507

# Submission time Handle Problem Language Result Execution time Memory
864507 2023-10-23T06:03:58 Z maks007 Toll (BOI17_toll) C++14
18 / 100
 3000 ms 7484 KB 
// Bismi ALlah
#include "bits/stdc++.h"

using namespace std;

signed main () {
	int n, m, k, query;
	cin >> k >> n >> m >> query;
	vector<pair <int,int>> g[n];
	for(int i = 0; i < m; i ++) {
		int u, v;
		cin >> u >> v;
		int w;
		cin >> w;
		g[u].push_back({v, w});
	}
	priority_queue <pair <int,int>> q;
	vector <int> dist(n, 1e9);
	dist[0] = 0;
	q.push({0, 0});
	while(!q.empty()) {
		int v = q.top().second, cur_d = q.top().first;
		q.pop();
		if(cur_d > dist[v]) continue;
		for(auto [u, w] : g[v]) {
			if(dist[u] > dist[v] + w) {
				dist[u] = dist[v] + w;
				q.push({-dist[u], u});
			}
		}
	}
	while(query --) {
		int a, b;
		cin >> a >> b;
		if(a == 0) {
			if(dist[b] == 1e9) cout << -1 << "\n";
			else
			cout << dist[b] << "\n"; 
		}else {
			vector <int> dist2(n, 1e9);
			dist2[a] = 0;
			q.push({0, a});
			while(!q.empty()) {
				int v = q.top().second, cur_d = q.top().first;
				q.pop();
				if(cur_d > dist2[v]) continue;
					for(auto [u, w] : g[v]) {
					if(dist2[u] > dist2[v] + w) {
						dist2[u] = dist2[v] + w;
						q.push({-dist2[u], u});
					}
				}
			}
			if(dist2[b] == 1e9) cout << -1;
			else cout << dist2[b];
			cout << "\n";
		}
	}
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:25:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |   for(auto [u, w] : g[v]) {
      |            ^
toll.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |      for(auto [u, w] : g[v]) {
      |               ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 3984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3720 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 428 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 15 ms 492 KB Output is correct
8 Correct 16 ms 348 KB Output is correct
9 Correct 47 ms 3368 KB Output is correct
10 Correct 103 ms 4268 KB Output is correct
11 Correct 85 ms 3360 KB Output is correct
12 Correct 60 ms 3220 KB Output is correct
13 Correct 98 ms 3852 KB Output is correct
14 Correct 61 ms 2788 KB Output is correct
15 Correct 67 ms 2324 KB Output is correct
16 Correct 52 ms 2392 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 13 ms 604 KB Output is correct
9 Correct 7 ms 348 KB Output is correct
10 Correct 40 ms 4396 KB Output is correct
11 Correct 217 ms 5008 KB Output is correct
12 Correct 314 ms 6540 KB Output is correct
13 Correct 368 ms 7484 KB Output is correct
14 Correct 293 ms 5880 KB Output is correct
15 Correct 207 ms 3664 KB Output is correct
16 Correct 194 ms 3664 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 13 ms 604 KB Output is correct
9 Correct 7 ms 348 KB Output is correct
10 Correct 40 ms 4396 KB Output is correct
11 Correct 217 ms 5008 KB Output is correct
12 Correct 314 ms 6540 KB Output is correct
13 Correct 368 ms 7484 KB Output is correct
14 Correct 293 ms 5880 KB Output is correct
15 Correct 207 ms 3664 KB Output is correct
16 Correct 194 ms 3664 KB Output is correct
17 Execution timed out 3065 ms 5124 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 3984 KB Time limit exceeded
2 Halted 0 ms 0 KB -