제출 #1297239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297239		chaitanyamehta	Journey (NOI18_journey)	C++20	43 / 100	2 ms	580 KiB

journey

#include <bits/stdc++.h>
using namespace std;

// Print u128 (helper)
string toStringUnsigned128(__uint128_t x) {
    if (x == 0) return "0";
    string s;
    while (x > 0) {
        int digit = (int)(x % 10);
        s.push_back('0' + digit);
        x /= 10;
    }
    reverse(s.begin(), s.end());
    return s;
}

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

    const unsigned long long OUT_LIM = 500000001ULL; // output cap
    const __uint128_t INTERNAL_CAP = (__uint128_t)10000000000000000000ULL; // 1e19, safe internal cap

    int n, m, h;
    if (!(cin >> n >> m >> h)) return 0;

    // S[j] = list of flights arriving to j: pairs (from_i, stay_t)
    vector<vector<pair<int,int>>> S(n);
    for (int i = 0; i <= n-2; ++i) {
        for (int r = 0; r < h; ++r) {
            int j, t;
            cin >> j >> t;
            // only keep flights that go strictly closer to Brasilia (j > i)
            if (j > i && j < n) {
                S[j].emplace_back(i, t);
            }
        }
    }

    if (m <= 0) return 0;

    // dp[c][d] = number of ways to reach city c in <= d nights (cumulative), using internal big integers
    vector<vector<__uint128_t>> dp(n, vector<__uint128_t>(m, 0));

    // Base: at city 0 (Amman) there is exactly 1 way to be there with 0 nights (start)
    dp[0][0] = 1;

    // D = 0: compute for cities > 0 (only flights with t == 0 can contribute)
    for (int C = 1; C < n; ++C) {
        __uint128_t s = 0;
        for (auto &pr : S[C]) {
            int i = pr.first;
            int t = pr.second;
            if (0 - t >= 0) { // only t == 0
                s += dp[i][0 - t];
                if (s >= INTERNAL_CAP) { s = INTERNAL_CAP; break; }
            }
        }
        dp[C][0] = s;
    }

    // D >= 1
    for (int D = 1; D < m; ++D) {
        dp[0][D] = dp[0][D-1]; // stay at Amman
        for (int C = 1; C < n; ++C) {
            __uint128_t val = dp[C][D-1]; // ways that were already at C and waited
            for (auto &pr : S[C]) {
                int i = pr.first;
                int t = pr.second;
                int prevD = D - t;
                if (prevD >= 0) {
                    val += dp[i][prevD];
                    if (val >= INTERNAL_CAP) { val = INTERNAL_CAP; break; }
                }
            }
            if (val >= INTERNAL_CAP) val = INTERNAL_CAP;
            dp[C][D] = val;
        }
    }

    // output exact counts for city n-1, days 0..m-1
    for (int D = 0; D < m; ++D) {
        __uint128_t cum = dp[n-1][D];
        __uint128_t prev = (D == 0 ? (__uint128_t)0 : dp[n-1][D-1]);
        __uint128_t exact = (cum >= prev ? cum - prev : 0);

        unsigned long long out;
        if (exact >= (__uint128_t)OUT_LIM) out = OUT_LIM;
        else out = (unsigned long long)(exact);

        cout << out << (D+1 < m ? ' ' : '\n');
    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 23 / 23
• Subtask 3: 0 / 26
• Subtask 4: 0 / 31