Submission #1318285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318285		LIA	Board Game (JOI24_boardgame)	C++17	3 / 100	4100 ms	242660 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (ll i = s; i < e; ++i)

ll n, m, k;
v<v<ll>> g;
string s;
v<ll> x;
bool stop(ll u) { return s[u] == '1'; }
const ll inf = 1e18;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  g.resize(n + 1);

  lp(i, 0, m) {
    ll a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  cin >> s;
  s = " " + s;
  x.resize(k + 1);
  lp(i, 1, k + 1) cin >> x[i];
  v<ll> sc;
  lp(i, 1, n + 1) if (stop(i)) sc.push_back(i);
  if (sc.empty()) {
    v<ll> d(n + 1, -1);
    queue<ll> q;
    d[x[1]] = 0;
    q.push(x[1]);
    while (!q.empty()) {
      ll u = q.front();
      q.pop();
      for (ll w : g[u])
        if (d[w] == -1) {
          d[w] = d[u] + 1;
          q.push(w);
        }
    }
    lp(i, 1, n + 1) cout << d[i] << "\n";
    return 0;
  }

  v<ll> ds(n + 1, inf);
  {
    queue<ll> q;
    for (ll u : sc) {
      ds[u] = 0;
      q.push(u);
    }
    while (!q.empty()) {
      ll u = q.front();
      q.pop();
      for (ll w : g[u])
        if (ds[w] > ds[u] + 1) {
          ds[w] = ds[u] + 1;
          q.push(w);
        }
    }
  }

  v<ll> pc(n + 1, inf);
  lp(i, 1, n + 1) {
    ll mn = inf;
    for (ll u : g[i])
      mn = min(mn, ds[u]);
    if (mn != inf)
      pc[i] = 1 + mn;
  }

  v<ll> ns(n + 1, -1);
  {
    for (ll u : sc)
      ns[u] = u;
    queue<ll> q;
    for (ll u : sc)
      q.push(u);
    while (!q.empty()) {
      ll u = q.front();
      q.pop();
      for (ll w : g[u])
        if (ns[w] == -1) {
          ns[w] = ns[u];
          q.push(w);
        }
    }
  }

  v<ll> ap(n + 1, -1);
  lp(i, 1, n + 1) {
    ll best = -1, mn = inf;
    for (ll u : g[i])
      if (ds[u] < mn) {
        mn = ds[u];
        best = u;
      }
    if (best != -1)
      ap[i] = ns[best];
  }

  if (k == 2) {
    map<tuple<ll, ll, ll>, ll> d;
    priority_queue<tuple<ll, ll, ll, ll>, v<tuple<ll, ll, ll, ll>>, greater<>>
        pq;

    d[{x[1], x[2], 0}] = 0;
    pq.push({0, x[1], x[2], 0});

    while (!pq.empty()) {
      auto [c, p1, p2, t] = pq.top();
      pq.pop();
      if (d[{p1, p2, t}] < c)
        continue;

      if (t == 0) {
        for (ll w : g[p1]) {
          ll nt = stop(w) ? 1 : 0;
          auto st = make_tuple(w, p2, nt);
          if (!d.count(st) || d[st] > c + 1) {
            d[st] = c + 1;
            pq.push({c + 1, w, p2, nt});
          }
        }
      } else {
        for (ll w : g[p2]) {
          ll nt = stop(w) ? 0 : 1;
          auto st = make_tuple(p1, w, nt);
          if (!d.count(st) || d[st] > c + 1) {
            d[st] = c + 1;
            pq.push({c + 1, p1, w, nt});
          }
        }
      }
    }

    lp(i, 1, n + 1) {
      ll ans = inf;
      for (auto [st, c] : d)
        if (get<0>(st) == i)
          ans = min(ans, c);
      cout << ans << "\n";
    }
    return 0;
  }

  v<ll> pos(k + 1);
  lp(i, 2, k + 1) pos[i] = x[i];
  const ll maxr = 300;
  v<ll> rc(maxr);
  lp(r, 0, maxr) {
    ll c = 0;
    lp(i, 2, k + 1) c += pc[pos[i]];
    rc[r] = c;
    lp(i, 2, k + 1) pos[i] = ap[pos[i]];
  }
  const ll inf = 1e18;
  v<v<array<ll, 2>>> dp(n + 1, v<array<ll, 2>>(maxr, {inf, inf}));
  priority_queue<tuple<ll, ll, ll, ll>, v<tuple<ll, ll, ll, ll>>, greater<>> pq;
  dp[x[1]][0][0] = 0;
  pq.push({0, x[1], 0, 0});
  while (!pq.empty()) {
    auto [c, u, r, w] = pq.top();
    pq.pop();
    if (w == 0) {
      for (ll v : g[u]) {
        ll nw = stop(v) ? 1 : 0;
        if (c + 1 < dp[v][r][nw]) {
          dp[v][r][nw] = c + 1;
          pq.push({c + 1, v, r, nw});
        }
      }
    } else {
      if (r < maxr - 1) {
        ll nc = c + rc[r];
        if (nc < dp[u][r + 1][0]) {
          dp[u][r + 1][0] = nc;
          pq.push({nc, u, r + 1, 0});
        }
      }
    }
  }

  lp(i, 1, n + 1) {
    ll ans = inf;
    lp(r, 0, maxr) {
      ans = min(ans, dp[i][r][0]);
      ans = min(ans, dp[i][r][1]);
    }
    cout << ans << '\n';
  }

  return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 9
• Subtask 7: 0 / 23
• Subtask 8: 0 / 9