Submission #1318334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318334		LIA	Board Game (JOI24_boardgame)	C++17	100 / 100	1407 ms	7000 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)
#define pll pair<ll, ll>

const ll inf = 1e18;
ll n, m, k;
v<v<ll>> g;
v<ll> type, dist1, dist2, c, csum, ans, dist;

struct state {
  ll idx, cnt, val, jump;
  bool operator<(const state &b) const {
    return val - csum[cnt] > b.val - csum[b.cnt];
  }
};

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> k;
  g.resize(n);
  type.assign(n, 0);
  dist1.assign(n, inf);
  dist2.assign(n, inf);
  c.assign(n + 2, 0);
  csum.assign(n + 2, 0);
  ans.assign(n, inf);
  dist.assign(n, inf);

  lp(i, 0, m) {
    ll a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  string s;
  cin >> s;
  ll st;
  cin >> st;
  st--;
  lp(i, 0, n) {
    if (s[i] == '1') {
      bool can = 0;
      for (ll nx : g[i])
        can |= (s[nx] == '1');
      type[i] = can ? 2 : 1;
    }
  }

  queue<ll> q;
  lp(i, 0, n) {
    if (type[i] == 1) {
      dist1[i] = 0;
      q.push(i);
    }
  }
  while (!q.empty()) {
    ll node = q.front();
    q.pop();
    for (ll it : g[node]) {
      if (dist1[it] > dist1[node] + 1) {
        dist1[it] = dist1[node] + 1;
        q.push(it);
      }
    }
  }

  deque<ll> dq;
  lp(i, 0, n) {
    if (type[i] == 2) {
      dist2[i] = 0;
      dq.push_back(i);
    }
  }
  while (!dq.empty()) {
    ll node = dq.front();
    dq.pop_front();
    for (ll it : g[node]) {
      ll w = (type[node] == 1 ? 0 : 1);
      if (dist2[it] > dist2[node] + w) {
        dist2[it] = dist2[node] + w;
        if (w == 0)
          dq.push_front(it);
        else
          dq.push_back(it);
      }
    }
  }

  lp(i, 0, k - 1) {
    ll x;
    cin >> x;
    x--;

    if (dist2[x] >= inf) {
      if (!type[x]) {
        c[1] += dist1[x];
        c[2] += -dist1[x] + 2;
      } else {
        c[1] += 2;
      }
    } else if (dist1[x] >= inf) {
      if (!type[x]) {
        c[1] += dist2[x];
        c[2] += -dist2[x] + 1;
      } else {
        c[1] += 1;
      }
    } else if (!type[x]) {
      if (dist1[x] >= dist2[x]) {
        c[1] += dist2[x];
        c[2] += -dist2[x] + 1;
      } else {
        c[1] += dist1[x];
        c[2] += -dist1[x] + 2;
        c[min(n + 1, 2 + dist2[x] - dist1[x])] -= 1;
      }
    } else if (type[x] == 1) {
      c[1] += 2;
      c[dist2[x]] -= 1;
    } else {
      c[1] += 1;
    }
  }

  ll add = 0;
  lp(i, 1, n + 2) {
    add += c[i];
    c[i] = add;
    csum[i] = csum[i - 1] + c[i];
  }

  priority_queue<state> pq;
  pq.push({st, 0, 0, 0});
  dist[st] = 0;

  while (!pq.empty()) {
    auto [idx, cnt, val, jump] = pq.top();
    pq.pop();

    if (cnt > n)
      continue;
    ans[idx] = min(ans[idx], val);

    if (jump) {
      if (val > dist[idx])
        continue;
      pq.push({idx, cnt, val + c[cnt], 0});
      continue;
    }

    for (ll nx : g[idx]) {
      if (val + 1 >= dist[nx])
        continue;
      dist[nx] = val + 1;
      if (type[nx])
        pq.push({nx, cnt + 1, val + 1, 1});
      else
        pq.push({nx, cnt, val + 1, 0});
    }
  }

  lp(i, 0, n) cout << ans[i] << '\n';
  return 0;
}

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