oj.uz

Submission #1014429

# Submission time Handle Problem Language Result Execution time Memory
1014429 2024-07-04T21:12:46 Z tanisha Drivers (BOI24_drivers) C++14
0 / 100
 2000 ms 6096 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int MAX_N = 200001;

vector<pair<int, int>> graph[MAX_N];
bool visited[MAX_N];

bool can_reach_safely(int start, int end, int max_time) {
    memset(visited, 0, sizeof(visited));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, start});

    while (!pq.empty()) {
        int time = pq.top().first;
        int city = pq.top().second;
        pq.pop();

        if (city == end) return true;
        if (visited[city]) continue;
        visited[city] = true;

        for (const auto& [next_city, travel_time] : graph[city]) {
            if (travel_time > max_time) continue;
            int new_time = time + travel_time;
            pq.push({(new_time <= max_time) ? new_time : travel_time, next_city});
        }
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, U;
    cin >> N >> M >> U;

    for (int i = 0; i < M; ++i) {
        int x, y, t;
        cin >> x >> y >> t;
        graph[x].emplace_back(y, t);
        graph[y].emplace_back(x, t);
    }

    for (int i = 0; i < U; ++i) {
        int a, b, p;
        cin >> a >> b >> p;
        cout << (can_reach_safely(a, b, p) ? "TAIP\n" : "NE\n");
    }

    return 0;
}

Compilation message

Main.cpp: In function 'bool can_reach_safely(int, int, int)':
Main.cpp:28:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |         for (const auto& [next_city, travel_time] : graph[city]) {
      |                          ^

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 25 ms 5468 KB Output is correct
3 Correct 5 ms 5468 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Execution timed out 2086 ms 6096 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 5 ms 5212 KB Output is correct
4 Correct 22 ms 5212 KB Output is correct
5 Correct 14 ms 5208 KB Output is correct
6 Correct 10 ms 5212 KB Output is correct
7 Correct 8 ms 5468 KB Output is correct
8 Correct 67 ms 5468 KB Output is correct
9 Correct 24 ms 5464 KB Output is correct
10 Correct 113 ms 5468 KB Output is correct
11 Correct 269 ms 5464 KB Output is correct
12 Correct 316 ms 6044 KB Output is correct
13 Correct 6 ms 5464 KB Output is correct
14 Correct 17 ms 5528 KB Output is correct
15 Correct 2 ms 5208 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5208 KB Output is correct
18 Correct 46 ms 5420 KB Output is correct
19 Execution timed out 2047 ms 5996 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 5208 KB Output is correct
2 Correct 25 ms 5468 KB Output is correct
3 Correct 5 ms 5468 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Execution timed out 2086 ms 6096 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 5208 KB Output is correct
2 Correct 25 ms 5468 KB Output is correct
3 Correct 5 ms 5468 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Execution timed out 2086 ms 6096 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 5208 KB Output is correct
2 Correct 25 ms 5468 KB Output is correct
3 Correct 5 ms 5468 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Execution timed out 2086 ms 6096 KB Time limit exceeded
6 Halted 0 ms 0 KB -