Submission #1308227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308227		lyra_g13	Journey (NOI18_journey)	C++20	43 / 100	2094 ms	572 KiB

journey

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

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

  ll n, maxnights, h;
  cin >> n >> maxnights >> h;

  vector<ll> vis(n), depth(n, -1e8);
  vector<vector<pair<ll, ll>>> adj(n), radj(n);
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < h; j++) {
      ll a, b;
      cin >> a >> b;
      adj[i].push_back({a, b});
      radj[a].push_back({i, b});
    }
  }

  depth[n - 1] = 0;
  auto dfs = [&](auto &&self, ll u) {
    if (vis[u])
      return;
    vis[u] = 1;
    for (auto [x, y] : radj[u]) {
      if (vis[x])
        continue;
      self(self, x);
    }
  };
  dfs(dfs, n - 1);

  map<ll, ll> m;
  auto dfs1 = [&](auto &&self, ll u, ll stay) {
    if (stay >= maxnights)
      return;
    if (u == n - 1) {
      m[stay] = min(500000000LL, m[stay] + 1);
      return;
    }
    if (vis[u] == 0 or vis[u] == 2)
      return;
    vis[u] = 2;
    for (auto [x, y] : adj[u]) {
      if ((vis[x] == 1 and x > u)) {
        for (int l = y; stay + l < maxnights; l++)
          self(self, x, stay + l);
      }
    }
    vis[u] = 1;
  };

  dfs1(dfs1, 0, 0);
  for (auto [x, y] : m) {
    cout << y << "\n";
  }
}

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