oj.uz

Submission #1014432

# Submission time Handle Problem Language Result Execution time Memory
1014432 2024-07-04T21:15:09 Z tanisha Drivers (BOI24_drivers) C++14
0 / 100
 2000 ms 5960 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& edge : graph[city]) {
            int next_city = edge.first;
            int travel_time = edge.second;
            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].push_back({y, t});
        graph[y].push_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;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 26 ms 5512 KB Output is correct
3 Correct 4 ms 5468 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Execution timed out 2096 ms 5740 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 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 4 ms 5212 KB Output is correct
4 Correct 19 ms 5212 KB Output is correct
5 Correct 12 ms 5212 KB Output is correct
6 Correct 10 ms 5212 KB Output is correct
7 Correct 7 ms 5468 KB Output is correct
8 Correct 70 ms 5548 KB Output is correct
9 Correct 26 ms 5468 KB Output is correct
10 Correct 116 ms 5464 KB Output is correct
11 Correct 273 ms 5552 KB Output is correct
12 Correct 331 ms 5960 KB Output is correct
13 Correct 4 ms 5464 KB Output is correct
14 Correct 18 ms 5428 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 1 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 46 ms 5396 KB Output is correct
19 Execution timed out 2084 ms 5732 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 5212 KB Output is correct
2 Correct 26 ms 5512 KB Output is correct
3 Correct 4 ms 5468 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Execution timed out 2096 ms 5740 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 5212 KB Output is correct
2 Correct 26 ms 5512 KB Output is correct
3 Correct 4 ms 5468 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Execution timed out 2096 ms 5740 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 5212 KB Output is correct
2 Correct 26 ms 5512 KB Output is correct
3 Correct 4 ms 5468 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Execution timed out 2096 ms 5740 KB Time limit exceeded
6 Halted 0 ms 0 KB -