oj.uz

Submission #472566

# Submission time Handle Problem Language Result Execution time Memory
472566 2021-09-13T18:06:25 Z Hamed5001 Toll (BOI17_toll) C++14
18 / 100
 3000 ms 6544 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mxN = 5e4, OO = 2e16;
ll preprocess[mxN];
bool vis[mxN];
ll COST[mxN];
vector<pair<ll, ll>> adj[mxN];
ll K, N, M, O;

void pre(ll st) {
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
	pq.push({0, st});
	preprocess[st] = 0;

	while(!pq.empty()) {
		ll node = pq.top().second;
		ll cost = pq.top().first;
		pq.pop();

		for (auto c : adj[node]) {
			if (cost + c.first < preprocess[c.second]) {
				preprocess[c.second] = cost + c.first;
				pq.push({cost + c.first, c.second});	
			}
		}
	}
}

ll dijkstra(ll st, ll en) {
	for (int i = 0; i < N; i++)
		COST[i] = OO;
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
	pq.push({0, st});
	COST[st] = 0;

	while(!pq.empty()) {
		ll node = pq.top().second;
		ll cost = pq.top().first;
		if (node == en) return cost;

		pq.pop();
		for (auto c : adj[node]) {
			if (cost + c.first < COST[c.second]) {
				COST[c.second] = cost + c.first;
				pq.push({cost + c.first, c.second});	
			}
		}
	}
	return -1;
}

void solve() {
	cin >> K >> N >> M >> O;

	for (int i = 0; i < N; i++)
		preprocess[i] = OO;
	
	for (ll i = 0; i < M; i++) {
		ll u, v, t;
		cin >> u >> v >> t;
		adj[u].push_back({t, v});
	}
	pre(0);

	while(O--) {
		ll a, b;
		cin >> a >> b;
		if (a == 0) {
			if (preprocess[b] == OO) preprocess[b] = -1;
			cout << preprocess[b] << endl;
		}
		else {
			cout << dijkstra(a, b) << endl;
		}
	}
}

int main() {
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1
0 / 7.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4516 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 19 ms 1484 KB Output is correct
8 Correct 19 ms 1608 KB Output is correct
9 Correct 38 ms 3360 KB Output is correct
10 Correct 79 ms 5768 KB Output is correct
11 Correct 62 ms 4508 KB Output is correct
12 Correct 48 ms 3924 KB Output is correct
13 Correct 74 ms 6440 KB Output is correct
14 Correct 53 ms 4292 KB Output is correct
15 Correct 38 ms 3744 KB Output is correct
16 Correct 38 ms 3652 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 4 ms 1612 KB Output is correct
8 Correct 8 ms 1612 KB Output is correct
9 Correct 6 ms 1484 KB Output is correct
10 Correct 28 ms 3788 KB Output is correct
11 Correct 168 ms 4676 KB Output is correct
12 Correct 227 ms 6112 KB Output is correct
13 Correct 270 ms 6544 KB Output is correct
14 Correct 216 ms 5424 KB Output is correct
15 Correct 148 ms 3908 KB Output is correct
16 Correct 127 ms 3892 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 4 ms 1612 KB Output is correct
8 Correct 8 ms 1612 KB Output is correct
9 Correct 6 ms 1484 KB Output is correct
10 Correct 28 ms 3788 KB Output is correct
11 Correct 168 ms 4676 KB Output is correct
12 Correct 227 ms 6112 KB Output is correct
13 Correct 270 ms 6544 KB Output is correct
14 Correct 216 ms 5424 KB Output is correct
15 Correct 148 ms 3908 KB Output is correct
16 Correct 127 ms 3892 KB Output is correct
17 Execution timed out 3059 ms 4876 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 3069 ms 3856 KB Time limit exceeded
2 Halted 0 ms 0 KB -