Submission #1307820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307820		lyra_g13	Journey (NOI18_journey)	C++20	0 / 100	1 ms	568 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; 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});
    }
  }

  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);
    }
  };

  vector<ll> visd(n);
  depth[0] = 0;
  auto depthdfs = [&](auto &&self, ll u) {
    if (vis[u] == 0)
      return;
    if (visd[u])
      return;
    visd[u] = 1;
    for (auto [x, y] : adj[u]) {
      if (visd[x])
        continue;
      depth[x] = min(depth[x], depth[u] + 1);
      self(self, x);
    }
  };

  vector<ll> ans;
  auto dfs1 = [&](auto &&self, ll u, ll stay) {
    if (u == n - 1) {
      if (stay <= maxnights)
        ans.push_back(stay);
      return;
    }
    if (vis[u] == 0 or vis[u] == 2)
      return;
    vis[u] = 2;
    for (auto [x, y] : adj[u]) {
      if (!(vis[u] == 0 or vis[u] == 2 or depth[x] < depth[u])) {
        self(self, x, stay + y);
      }
    }
    vis[u] = 1;
  };

  depthdfs(depthdfs, 0);
  dfs(dfs, n - 1);
  dfs1(dfs1, 0, 0);
  for (auto i : ans) {
    cout << i << "\n";
  }
}

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