Submission #1033668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033668		pdao	Trains (BOI24_trains)	C++17	8 / 100	2093 ms	1048576 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pb push_back

using namespace std;

const int maxn = 1e5 + 5;
vector<vector<int>> child(maxn, vector<int>(0));
int ways[maxn]; // ways[i] is number of way to travel the whole town from i

void dfs(int i) {
  if (child[i].empty()) ways[i] = 1;
  else {
    ways[i] = 0;
    for (int x : child[i]) {
      dfs(x);
      ways[i] += ways[x];
    }

    ways[i] += 1;
  }
}

signed main() {
  int n, d, x; cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> d >> x;
    if (d > 0)
      for (int j = 1; j <= x; j++) {
        if (i + j * d > n) break;
        child[i].pb(i + j * d);
      }
  }

  dfs(1);

  cout << ways[1];
}

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