Submission #1223810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223810		abczz	Board Game (JOI24_boardgame)	C++20	100 / 100	2311 ms	96028 KiB

Main

#include <iostream>
#include <queue>
#include <vector>
#include <array>
#include <algorithm>
#include <cmath>
#define ll long long

using namespace std;

array<ll, 2> operator+(array<ll, 2> a, array<ll, 2> b) {
  return {a[0]+b[0], a[1]+b[1]};
}
queue <ll> Q;
vector <array<ll, 2>> st;
priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq, U[2];
vector <ll> adj[50000], X;
string S;
ll dp[50000][225], mn[50000];
array <ll, 2> stop[50001];
bool B[50000];
ll n, m, k, a, b, rt, dist[50000], dist2[50000], F[50000], cost[50000];
void search(ll k, ll dlt) {
  for (int i=0; i<n; ++i) cost[i] = (ll)1e18;
  for (auto [u, w] : st) {
    for (auto v : adj[u]) {
      if (cost[v] > w+k+1) {
        cost[v] = w+k+1;
        pq.push({w+k+1, v});
      }
    }
  }
  while (!pq.empty()) {
    auto [w, u] = pq.top();
    pq.pop();
    if (cost[u] != w) continue;
    for (auto v : adj[u]) {
      if (cost[v] > cost[u] + 1 + (S[u] == '1' ? k : 0)) {
        cost[v] = cost[u] + 1 + (S[u] == '1' ? k : 0);
        pq.push({cost[v], v});
      }
    }
  }
  for (int i=0; i<n; ++i) F[i] = min(F[i], cost[i]+dlt);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m >> k;
  for (int i=0; i<m; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  cin >> S;
  for (int i=0; i<n; ++i) {
    dist[i] = F[i] = mn[i] = (ll)1e18;
    if (S[i] == '1') Q.push(i), dist[i] = 0;
    for (int j=0; j<225; ++j) dp[i][j] = (ll)1e18;
  }
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    for (auto v : adj[u]) {
      if (dist[v] == (ll)1e18) {
        dist[v] = dist[u] + 1;
        Q.push(v);
      }
    }
  }
  for (int i=0; i<n; ++i) {
    dist2[i] = (ll)1e18;
    if (S[i] == '1') {
      bool ok = 0;
      for (auto v : adj[i]) ok |= (S[v] == '1');
      if (ok) pq.push({0, i}), dist2[i] = 0;
    }
  }
  while (!pq.empty()) {
    auto [w, u] = pq.top();
    pq.pop();
    if (dist2[u] != w) continue;
    for (auto v : adj[u]) {
      if (dist2[v] > dist2[u] + (S[v] == '0')) {
        dist2[v] = dist2[u] + (S[v] == '0');
        pq.push({dist2[v], v});
      }
    }
  }
  ll s = 0;
  for (int i=0; i<n; ++i) {
    if (dist[i] && dist[i] != (ll)1e18) dist[i] -= 2;
    if (dist2[i] && S[i] == '1') ++dist2[i];
    if (dist2[i] && dist2[i] != (ll)1e18) --dist2[i];
  }
  for (int i=0; i<k; ++i) {
    cin >> a;
    --a;
    if (!i) rt = a;
    else X.push_back(a), s += dist[a];
  }
  Q.push(rt);
  F[rt] = 0;
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    for (auto v : adj[u]) {
      if (F[v] > F[u]+1) {
        F[v] = F[u]+1;
        if (S[v] != '1') Q.push(v);
      }
    }
  }
  for (int i=0; i<n; ++i) {
    if (F[i] != (ll)1e18 && S[i] == '1') st.push_back({i, F[i]}), B[i] = 1;
  }
  if (st.empty() || (st.size() == 1 && st[0][0] == rt)) {
    for (int i=0; i<n; ++i) cout << F[i] << '\n';
    return 0;
  }
  sort(X.begin(), X.end(), [](auto a, auto b) {
    return dist2[a]-dist[a] < dist2[b]-dist[b];
  });
  if (k <= (ll)sqrt(n)) {
    search(2*X.size(), s);
    for (int i=0; i<X.size(); ++i) {
      if (dist2[X[i]] == (ll)1e18) break;
      s -= dist[X[i]]-dist2[X[i]];
      search(2*X.size()-i-1, s);
    }
  }
  else {
    for (auto u : X) {
      if (dist2[u] == (ll)1e18) continue;
      stop[max(0LL, dist2[u]-dist[u])] = stop[max(0LL, dist2[u]-dist[u])] + array<ll, 2>{-1, dist2[u]-dist[u]};
    }
    stop[0] = stop[0] + array<ll, 2>{2*(ll)X.size(), s};
    for (int i=1; i<n; ++i) {
      stop[i] = stop[i-1] + stop[i];
    }
    mn[rt] = dp[rt][0] = 0;
    U[0].push({0, rt});
    for (int t=0; t<n; ++t) {
      if (U[0].empty()) break;
      while (!U[0].empty()) {
        auto [w, u] = U[0].top();
        U[0].pop();
        if (dp[u][t-mn[u]] != w) break;
        for (auto v : adj[u]) {
          if (mn[v] == 1e18) mn[v] = t + (S[v] == '1');
          if (t+(S[v]=='1')-mn[v] < 225 && dp[v][t+(S[v]=='1')-mn[v]] > w+1) {
            dp[v][t+(S[v]=='1')-mn[v]] = w+1;
            U[S[v]=='1'].push({w+1, v});
          }
        }
      }
      swap(U[0], U[1]);
    }
    for (int i=0; i<n; ++i) {
      for (int j=0; j<225; ++j) {
        if (dp[i][j] == (ll)1e18 || (j == 0 && mn[i] == 0)) continue;
        ll u = mn[i]+j-(S[i] == '1');
        if (u <= 0) continue;
        F[i] = min(F[i], dp[i][j] + u * stop[u][0] + stop[u][1]);
      }
    }
  }
  for (int i=0; i<n; ++i) cout << F[i] << '\n';
}

• 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