Submission #1033601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033601		don_ban_tinh	Trains (BOI24_trains)	C++14	0 / 100	2098 ms	2260 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;

const int MOD = 1000000007;

int main() {
    int N;
    scanf("%d", &N);

    vector<pair<int, int>> routes(N + 1);
    for (int i = 1; i <= N; ++i) {
        int d, x;
        scanf("%d%d", &d, &x);
        routes[i] = {d, x};
    }

    vector<bool> visited(N + 1, false);
    vector<long long> dp(N + 1, 0);
    dp[1] = 1;

    queue<int> q;
    q.push(1);
    visited[1] = true;

    while (!q.empty()) {
        int city = q.front();
        q.pop();

        int d = routes[city].first;
        int x = routes[city].second;

        if (d > 0) {
            for (int t = 1; t <= x; ++t) {
                int next_city = city + t * d;
                if (next_city <= N) {
                    if (!visited[next_city]) {
                        q.push(next_city);
                        visited[next_city] = true;
                    }
                    dp[next_city] = (dp[next_city] + dp[city]) % MOD;
                } else {
                    break;
                }
            }
        }
    }

    long long result = 0;
    for (int i = 1; i <= N; ++i) {
        result = (result + dp[i]) % MOD;
    }

    printf("%lld", result);

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d%d", &d, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29