oj.uz

Submission #1111594

# Submission time Handle Problem Language Result Execution time Memory
1111594 2024-11-12T09:51:53 Z jmuzhen Drivers (BOI24_drivers) C++17
0 / 100
 2000 ms 1576 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long

using ii = pair<int, int>;
vector<vector<ii>> adj;

int n, m, u;

/* observation: abs(dist(a, x) - dist(b, x)) <= dist(a, b) <= dist(a, x) + dist(b, x)
 * in fact, only the left half is useful.
 * The answer is YES, iff we can find some abs(dist(a, x) - dist(b, x)) <= p (the query value).
 */
 
 
auto dijkstra(int src, int p) {
	vector<int> dist(n+1, 1e15);
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	
	dist[src] = 0; pq.push({0, src});
	while (!pq.empty()) {
		auto [d, u] = pq.top(); pq.pop();
		if (d > dist[u]) continue;
		for (auto [v, w] : adj[u]) {
			if (w > p) continue;
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				pq.push({dist[v], v});
			}
		}	
	}
	return dist;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	cin >> n >> m >> u;
	// all nodes are 1-indexed.
	adj = vector<vector<ii>>(n+1, vector<ii>());
	
	for (int i = 0; i < m; i++) {
		int a, b, t; cin >> a >> b >> t;
		adj[a].push_back({b, t});
		adj[b].push_back({a, t});
	}
	
	
	
	
	// queries
	while (u--) {
		int a, b, p; cin >> a >> b >> p;
		auto dist = dijkstra(a, p);
		if (dist[b] < 1e14) {
			cout << "TAIP\n";
		}
		else {
			cout << "NE\n";
		}
	}

}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 6 ms 592 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Execution timed out 2100 ms 1576 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 9 ms 540 KB Output is correct
5 Correct 9 ms 336 KB Output is correct
6 Correct 6 ms 336 KB Output is correct
7 Correct 4 ms 592 KB Output is correct
8 Correct 47 ms 664 KB Output is correct
9 Correct 7 ms 592 KB Output is correct
10 Correct 106 ms 752 KB Output is correct
11 Correct 216 ms 592 KB Output is correct
12 Correct 222 ms 848 KB Output is correct
13 Correct 4 ms 848 KB Output is correct
14 Correct 14 ms 592 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 38 ms 560 KB Output is correct
19 Execution timed out 2060 ms 1152 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 6 ms 592 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Execution timed out 2100 ms 1576 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 6 ms 592 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Execution timed out 2100 ms 1576 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 6 ms 592 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Execution timed out 2100 ms 1576 KB Time limit exceeded
6 Halted 0 ms 0 KB -