oj.uz

Submission #1111611

# Submission time Handle Problem Language Result Execution time Memory
1111611 2024-11-12T09:59:54 Z jmuzhen Drivers (BOI24_drivers) C++14
0 / 100
 7 ms 504 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).
 */
 
int org;
 
bool dfs(int u, int t, int p, vector<bool>& visited, int idx, vector<vector<unordered_map<int, bool>>> okt) {
	if (visited[u]) return false;
	if (u == t) return true;
	visited[u] = true;
	okt[idx][org][t] = true;
	for (auto [v, w] : adj[u]) {
		if (w > idx) continue;
		bool r = dfs(v, t, p, visited, idx, okt);
		if (r) return true;
	}
	return false;
}

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});
	}
	
	vector<vector<unordered_map<int, bool>>> okt(51, vector<unordered_map<int, bool>>(n+1, unordered_map<int, bool>()));
	for (int a = 1; a <= n; a++) {
		for (int i = 0; i <= 50; i++) {
		vector<bool> visited(n+1, false);
		dfs(a, 1e9, -1, visited, i, okt);
	}
	}
	// queries
	while (u--) {
		int a, b, p; cin >> a >> b >> p;
		
		auto ok = okt[a][b][p];
		if (ok) {
			cout << "TAIP\n";
		}
		else {
			cout << "NE\n";
		}
	}

}

Compilation message

Main.cpp: In function 'bool dfs(long long int, long long int, long long int, std::vector<bool>&, long long int, std::vector<std::vector<std::unordered_map<long long int, bool> > >)':
Main.cpp:23:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |  for (auto [v, w] : adj[u]) {
      |            ^

Subtask #1
0.0 / 10.0

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

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

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

Subtask #4
0.0 / 23.0

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

Subtask #5
0.0 / 45.0

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