Submission #50627338

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>

namespace {
    using ModInt [[maybe_unused]] = atcoder::modint998244353;
    using Num [[maybe_unused]] = long long int;
    using Vec [[maybe_unused]] = std::vector<Num>;
    using Set [[maybe_unused]] = std::set<Num>;
    using Mset [[maybe_unused]] = std::multiset<Num>;
    using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

    template<typename T>
    using Q [[maybe_unused]] = std::queue<T>;

    template<typename T>
    using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

void solve(std::istream& is, std::ostream& os) {
    Num n, m;
    is >> n >> m;

    std::vector<std::vector<std::tuple<Num, Num, Num, Num, Num>>> stations(n);
    std::optional<Num> lst_n;

    for(Num i{0}; i<m; ++i) {
        Num l, d, k, c, a, b;
        is >> l >> d >> k >> c >> a >> b;
        --a;
        --b;

        stations[b].push_back(std::make_tuple(a, l, d, k, c));
        if (b != (n-1)) {
            continue;
        }

        const Num lst = l + (k - 1) * d + c;
        if (!lst_n.has_value()) {
            lst_n = lst;
        } else {
            lst_n = std::max(lst_n.value(), lst);
        }
    }

    if (!lst_n.has_value()) {
        for(Num i{0}; i<(n-1); ++i) {
            os << "Unreachable\n";
        }
        return;
    }

    std::priority_queue<std::pair<Num, Num>> q;
    std::vector<std::optional<Num>> ts(n);
    ts.at(n-1) = lst_n.value();

    q.push(std::make_pair(lst_n.value(), n-1));
    while(!q.empty()) {
        const auto [src, from] = q.top();
        q.pop();

        std::map<Num, Num> tos;
        for(const auto& [to, l, d, k, c] : stations[from]) {
            const auto dst = src - c;
            if (dst < l) {
                continue;
            }

            const Num fst = l;
            const Num dept = l + std::clamp((dst - l) / d, 0LL, k-1) * d;

            if (tos.contains(to)) {
                tos[to] = std::max(tos[to], dept);
            } else {
                tos[to] = dept;
            }
        }

        for(const auto& [to, t] : tos) {
            if (!ts.at(to).has_value() || (ts.at(to).value() < t)) {
                ts.at(to) = t;
                q.push(std::make_pair(t, to));
            }
        }
    }

    for(Num i{0}; i<(n-1); ++i) {
        if (ts.at(i).has_value()) {
            os << ts.at(i).value() << "\n";
        } else {
            os << "Unreachable\n";
        }
    }
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve(std::istream&, std::ostream&)’:
Main.cpp:68:23: warning: unused variable ‘fst’ [-Wunused-variable]
   68 |             const Num fst = l;
      |                       ^~~

Judge Result