Submission #72521042

Source Code Expand

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, L;
    long long S, T;
    cin >> N >> M >> L >> S >> T;
    vector<vector<pair<int, long long>>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v; long long c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
    }
    vector<unordered_set<long long>> dp_prev(N + 1), dp_curr(N + 1);
    dp_prev[1].insert(0);
    for (int step = 1; step <= L; step++) {
        for (int u = 1; u <= N; u++)
            for (long long cost_so_far : dp_prev[u])
                for (auto &edge : adj[u]) {
                    int v = edge.first;
                    long long c = edge.second;
                    long long new_cost = cost_so_far + c;
                    if (new_cost <= T)
                        dp_curr[v].insert(new_cost);
                }
        dp_prev = dp_curr;
        for (int i = 1; i <= N; i++)
            dp_curr[i].clear();
    }
    vector<int> answer;
    for (int v = 1; v <= N; v++)
        for (long long cost : dp_prev[v])
            if (cost >= S && cost <= T) {
                answer.push_back(v);
                break;
            }
    sort(answer.begin(), answer.end());
    for (int i = 0; i < (int)answer.size(); i++) {
        if (i) cout << " ";
        cout << answer[i];
    }
    cout << "\n";
    return 0;
}

Submission Info

Submission Time
Task D - Paid Walk
User adityagrg023
Language C++23 (GCC 15.2.0)
Score 400
Code Size 1509 Byte
Status AC
Exec Time 374 ms
Memory 133300 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 57
Set Name Test Cases
Sample example_00.txt, example_01.txt, example_02.txt
All example_00.txt, example_01.txt, example_02.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, hand_12.txt, hand_13.txt, hand_14.txt, hand_15.txt, hand_16.txt, hand_17.txt, hand_18.txt, hand_19.txt, hand_20.txt, hand_21.txt, hand_22.txt, hand_23.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt
Case Name Status Exec Time Memory
example_00.txt AC 1 ms 3400 KiB
example_01.txt AC 1 ms 3524 KiB
example_02.txt AC 1 ms 3456 KiB
hand_00.txt AC 159 ms 84828 KiB
hand_01.txt AC 208 ms 91468 KiB
hand_02.txt AC 175 ms 90292 KiB
hand_03.txt AC 196 ms 90736 KiB
hand_04.txt AC 174 ms 86304 KiB
hand_05.txt AC 77 ms 36280 KiB
hand_06.txt AC 1 ms 3404 KiB
hand_07.txt AC 1 ms 3524 KiB
hand_08.txt AC 83 ms 34236 KiB
hand_09.txt AC 81 ms 34224 KiB
hand_10.txt AC 44 ms 29884 KiB
hand_11.txt AC 13 ms 29856 KiB
hand_12.txt AC 72 ms 36208 KiB
hand_13.txt AC 72 ms 36280 KiB
hand_14.txt AC 70 ms 36152 KiB
hand_15.txt AC 110 ms 51760 KiB
hand_16.txt AC 142 ms 64056 KiB
hand_17.txt AC 80 ms 34356 KiB
hand_18.txt AC 83 ms 34928 KiB
hand_19.txt AC 80 ms 34232 KiB
hand_20.txt AC 81 ms 34360 KiB
hand_21.txt AC 85 ms 34996 KiB
hand_22.txt AC 189 ms 90296 KiB
hand_23.txt AC 210 ms 91452 KiB
random_00.txt AC 71 ms 35132 KiB
random_01.txt AC 79 ms 35256 KiB
random_02.txt AC 77 ms 35132 KiB
random_03.txt AC 56 ms 35120 KiB
random_04.txt AC 78 ms 35164 KiB
random_05.txt AC 80 ms 35260 KiB
random_06.txt AC 62 ms 35056 KiB
random_07.txt AC 100 ms 46136 KiB
random_08.txt AC 83 ms 35872 KiB
random_09.txt AC 52 ms 34744 KiB
random_10.txt AC 79 ms 34928 KiB
random_11.txt AC 97 ms 42924 KiB
random_12.txt AC 76 ms 35896 KiB
random_13.txt AC 269 ms 109344 KiB
random_14.txt AC 145 ms 54160 KiB
random_15.txt AC 272 ms 111024 KiB
random_16.txt AC 84 ms 34176 KiB
random_17.txt AC 374 ms 133300 KiB
random_18.txt AC 66 ms 34276 KiB
random_19.txt AC 224 ms 82528 KiB
random_20.txt AC 85 ms 35256 KiB
random_21.txt AC 61 ms 34236 KiB
random_22.txt AC 78 ms 34224 KiB
random_23.txt AC 227 ms 84268 KiB
random_24.txt AC 56 ms 35104 KiB
random_25.txt AC 77 ms 35104 KiB
random_26.txt AC 77 ms 35104 KiB
random_27.txt AC 77 ms 35116 KiB
random_28.txt AC 79 ms 35172 KiB
random_29.txt AC 80 ms 35164 KiB