Submission #39260286

Source Code Expand

/*
Author: Aaron He
Created: 26 February 2023 (Sunday)
*/
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "helpers/debug.h"
#else
#define debug(...)
#endif

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n), rev_adj(n);
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < m; j++) {
      if (s[j] == '1') {
        adj[i].push_back(i + (j + 1));
        rev_adj[i + (j + 1)].push_back(i);
      }
    }
  }
  const int INF = 1e9;
  auto bfs = [&] (vector<vector<int>> &adj, int start) {
    queue<int> q;
    vector<int> dist(n, INF);
    q.push(start);
    dist[start] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int v : adj[u]) {
        if (dist[v] == INF) {
          dist[v] = dist[u] + 1;
          q.push(v);
        }
      }
    }
    return dist;
  };
  vector<int> dist_1 = bfs(adj, 0);
  vector<int> dist_n = bfs(rev_adj, n - 1);
  for (int i = 1; i < n - 1; i++) {
    int ans = INT_MAX;
    for (int j = max(0, i - m + 1); j < i; j++) {
      for (int k : adj[j]) {
        if (k > i) {
          ans = min(ans, dist_1[j] + 1 + dist_n[k]);
        }
      }
    }
    cout << (ans >= INF ? -1 : ans) << " \n"[n == n - 2];
  }
}

Submission Info

Submission Time
Task F - Teleporter and Closed off
User aaronhe
Language C++ (GCC 9.2.1)
Score 500
Code Size 1358 Byte
Status AC
Exec Time 88 ms
Memory 24144 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 50
Set Name Test Cases
Sample example_00.txt, example_01.txt
All colored_00.txt, colored_01.txt, colored_02.txt, colored_03.txt, colored_04.txt, colored_05.txt, colored_06.txt, colored_07.txt, colored_08.txt, colored_09.txt, colored_10.txt, colored_11.txt, colored_12.txt, colored_13.txt, colored_14.txt, colored_15.txt, colored_16.txt, colored_17.txt, colored_18.txt, colored_19.txt, colored_20.txt, colored_21.txt, colored_22.txt, colored_23.txt, colored_24.txt, colored_25.txt, example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt
Case Name Status Exec Time Memory
colored_00.txt AC 62 ms 15992 KiB
colored_01.txt AC 68 ms 15812 KiB
colored_02.txt AC 68 ms 16284 KiB
colored_03.txt AC 62 ms 16320 KiB
colored_04.txt AC 59 ms 17172 KiB
colored_05.txt AC 80 ms 18128 KiB
colored_06.txt AC 53 ms 14052 KiB
colored_07.txt AC 48 ms 15488 KiB
colored_08.txt AC 70 ms 16640 KiB
colored_09.txt AC 57 ms 14056 KiB
colored_10.txt AC 45 ms 14940 KiB
colored_11.txt AC 67 ms 16064 KiB
colored_12.txt AC 44 ms 12996 KiB
colored_13.txt AC 47 ms 15012 KiB
colored_14.txt AC 78 ms 16812 KiB
colored_15.txt AC 49 ms 13472 KiB
colored_16.txt AC 55 ms 15268 KiB
colored_17.txt AC 69 ms 16372 KiB
colored_18.txt AC 51 ms 13644 KiB
colored_19.txt AC 62 ms 15440 KiB
colored_20.txt AC 86 ms 20068 KiB
colored_21.txt AC 51 ms 14172 KiB
colored_22.txt AC 68 ms 16956 KiB
colored_23.txt AC 68 ms 17604 KiB
colored_24.txt AC 60 ms 14732 KiB
colored_25.txt AC 88 ms 21356 KiB
example_00.txt AC 5 ms 3592 KiB
example_01.txt AC 2 ms 3488 KiB
hand_00.txt AC 76 ms 24144 KiB
hand_01.txt AC 25 ms 8628 KiB
hand_02.txt AC 41 ms 15060 KiB
hand_03.txt AC 37 ms 14964 KiB
hand_04.txt AC 78 ms 23504 KiB
hand_05.txt AC 36 ms 15016 KiB
hand_06.txt AC 44 ms 14936 KiB
hand_07.txt AC 39 ms 14968 KiB
random_00.txt AC 71 ms 17580 KiB
random_01.txt AC 76 ms 18656 KiB
random_02.txt AC 5 ms 3592 KiB
random_03.txt AC 82 ms 18396 KiB
random_04.txt AC 77 ms 17600 KiB
random_05.txt AC 8 ms 3608 KiB
random_06.txt AC 80 ms 16816 KiB
random_07.txt AC 79 ms 16900 KiB
random_08.txt AC 4 ms 3464 KiB
random_09.txt AC 56 ms 14528 KiB
random_10.txt AC 66 ms 14676 KiB
random_11.txt AC 6 ms 3556 KiB
random_12.txt AC 44 ms 12636 KiB
random_13.txt AC 40 ms 12004 KiB