oj.uz

Submission #1111572

# Submission time Handle Problem Language Result Execution time Memory
1111572 2024-11-12T09:41:22 Z jmuzhen Drivers (BOI24_drivers) C++14
0 / 100
 1 ms 592 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) {
	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 (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});
	}
	
	
	// dijkstra
	auto dist = dijkstra(1);
	
	// queries
	while (u--) {
		int a, b, p ; cin >> a >> b >> p;
		int L = abs(dist[a] - dist[b]), R = dist[a] + dist[b];
		bool ok;
		if (p < L) ok = false;
		else if (p >= R) ok = true;
		else {
			int _;
			ok = ((_ & 1) == 0);
		}
		
		if (ok) {
			cout << "TAIP\n";
		}
		else {
			cout << "NE\n";
		}
	}

}

Compilation message

Main.cpp: In function 'auto dijkstra(long long int)':
Main.cpp:23:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |   auto [d, u] = pq.top(); pq.pop();
      |        ^
Main.cpp:25:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |   for (auto [v, w] : adj[u]) {
      |             ^
Main.cpp: In function 'int main()':
Main.cpp:60:8: warning: '_' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |    int _;
      |        ^

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 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 Incorrect 1 ms 592 KB Output isn't correct
3 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 Incorrect 1 ms 592 KB Output isn't correct
3 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 Incorrect 1 ms 592 KB Output isn't correct
3 Halted 0 ms 0 KB -