Codeforces Round #584 F. Koala and Notebook

https://codeforces.com/contest/1209/problem/F

Suppose that we already understand the official editorial. Official solution is really simple but I didn't come up with this algorithm without reading it. Instead, I will explain another way to compute the shortest distance.

If we maintain entire string, it consumes a lot of time, which takes O(nm) in the worst case. We want to avoid that. We define layer k as the vertices set which contains the vertices whose distance from 0 is equal to k. Let dp[u] be the answer for vertex u without modulo. We calculate dp[u] from the smallest layer to the largest layer. We assume that layer k or less are already computed, then compute layer k+1.

Consider the set of dp[u] in layer k. For simplicity, assume that they are "123", "124", "201", "223", "331". We can compress them by rank compression. That is, they are compressed into 0, 1, 2, 3, 4, respectively. In this representation, the length of string doesn't increase, so the time complexity doesn't increase quadratically.

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

using namespace std;
using ll = long long;

constexpr int MOD = 1000000007;

class mint {
  int n;
public:
  mint(int n_ = 0) : n(n_) {}
  explicit operator int() { return n; }
  friend mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
  friend mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
  friend mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
  friend mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
  friend mint &operator+=(mint &a, mint b) { return a = a + b; }
  friend mint &operator-=(mint &a, mint b) { return a = a - b; }
  friend mint &operator*=(mint &a, mint b) { return a = a * b; }
  friend bool operator==(mint a, mint b) { return a.n == b.n; }
  friend bool operator!=(mint a, mint b) { return a.n != b.n; }
  friend istream &operator>>(istream &i, mint &a) { return i >> a.n; }
  friend ostream &operator<<(ostream &o, mint a) { return o << a.n; }
};
mint operator "" _m(unsigned long long n) { return n; }

struct edge {
  int v;
  int w;
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N, M; cin >> N >> M;
  vector<vector<edge>> G(N);
  auto add = [&](int u, int v, int w) {
    string s = to_string(w);
    int x = u;
    for (int i = 0; i < s.size(); i++) {
      int y = i < s.size() - 1 ? G.size() : v;
      G[x].push_back((edge){y, s[i] - '0'});
      if (y == G.size()) G.emplace_back();
      x = y;
    }
  };
  rep(i, M) {
    int a, b; cin >> a >> b; a--; b--;
    add(a, b, i + 1);
    add(b, a, i + 1);
  }
  vector<int> level(G.size(), -1);
  queue<int> q;
  level[0] = 0;
  q.push(0);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (edge e : G[u]) {
      if (level[e.v] == -1) {
        level[e.v] = level[u] + 1;
        q.push(e.v);
      }
    }
  }
  int mx = *max_element(range(level));
  vector<vector<int>> vs(mx + 1);
  rep(i, G.size()) vs[level[i]].push_back(i);
  vector<int> str(G.size());
  vector<mint> ans(G.size());
  vector<pair<int, int>> yet(G.size(), make_pair(1e9, 1e9));
  for (int i = 0; i < mx; i++) {
    for (int u : vs[i]) {
      for (auto e : G[u]) {
        if (level[e.v] == i + 1) {
          if (yet[e.v] > make_pair(str[u], e.w)) {
            yet[e.v] = make_pair(str[u], e.w);
            ans[e.v] = ans[u] * 10 + e.w;
          }
        }
      }
    }
    vector<pair<int, int>> dic;
    for (int u : vs[i + 1]) dic.push_back(yet[u]);
    sort(range(dic));
    dic.erase(unique(range(dic)), dic.end());
    for (int u : vs[i + 1]) {
      str[u] = lower_bound(range(dic), yet[u]) - dic.begin();
    }
  }
  for (int i = 1; i < N; i++) {
    cout << ans[i] << '\n';
  }
}