Submission #978215

#	Time	Username	Problem	Language	Result	Execution time	Memory
978215		model_code	Board Game (JOI24_boardgame)	C++17	100 / 100	529 ms	52772 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template <class T>
using vc = vector<T>;

#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if

template <typename T>
T POP(deque<T> &que) {
  T a = que.front();
  que.pop_front();
  return a;
}

template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
  vector<int> ids(len(A));
  iota(all(ids), 0);
  sort(all(ids),
       [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ids;
}

// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
  vc<T> B(len(I));
  FOR(i, len(I)) B[i] = A[I[i]];
  return B;
}

constexpr ll INF = 1'000'000'000'000'000'000;

// 点集合 V からの距離
// 距離が x1 または x2 であり, f(u,v) で与える.
template <typename F>
vc<ll> bfs(int N, vc<vc<int>> &G, vc<int> &V, F f) {
  assert(!V.empty());
  vc<ll> dist(N, INF);
  deque<int> que;
  for (auto &v: V) { dist[v] = 0, que.push_back(v); }
  while (len(que)) {
    int v = POP(que);
    for (int w: G[v]) {
      ll x = f(v, w);
      assert(x == 0 || x == 1);
      if (chmin(dist[w], dist[v] + x)) {
        if (x == 0)
          que.push_front(w);
        else
          que.push_back(w);
      }
    }
  }
  return dist;
}

void out(vc<ll> ANS) {
  for (ll x: ANS) cout << x << "\n";
}

void solve() {
  // 入力を読み込む
  int N, M, K;
  cin >> N >> M >> K;
  vc<vc<int>> G(N);
  FOR(M) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    G[u].emplace_back(v), G[v].emplace_back(u);
  }
  string S;
  cin >> S;
  vc<int> X;
  FOR(K) {
    int x;
    cin >> x;
    X.emplace_back(--x);
  }

  // 駒 0 の初期位置：X0
  // この実装では「他の駒」の個数を K としている
  int X0 = X[0];
  X.erase(X.begin());
  --K;

  // 入力ここまで
  // åœæ­¢ãƒžã‚¹ãŒå­˜åœ¨ã—ãªã„å ´åˆ
  if (count(all(S), '1') == 0) {
    vc<int> V = {X0};
    vc<ll> ANS = bfs(N, G, V, [&](int u, int v) -> int { return 1; });
    return out(ANS);
  }

  // 駒 0 が目的達成までに他の駒がターンを消化する回数 n
  // n>=1 のときに 2n+a が利用できるような a の最小値
  vc<ll> A = [&]() -> vc<ll> {
    vc<int> V;
    FOR(v, N) {
      if (S[v] != '1') continue;
      for (int w: G[v]) { V.emplace_back(w); }
    }
    vc<ll> dist = bfs(N, G, V, [&](int u, int v) -> int { return 1; });
    vc<ll> A(K);
    FOR(k, K) {
      ll x = dist[X[k]];
      A[k] = x - 1;
    }
    return A;
  }();

  // n>=1 のときに n+b が利用できるような b の最小値
  vc<ll> B = [&]() -> vc<ll> {
    vc<int> V;
    FOR(v, N) {
      if (S[v] != '1') continue;
      for (int w: G[v]) {
        if (S[w] == '1') {
          V.emplace_back(v);
          break;
        }
      }
    }
    if (V.empty()) return vc<ll>(K, INF);
    vc<ll> dist = bfs(
        N, G, V, [&](int u, int v) -> int { return (S[u] == '1' ? 0 : 1); });
    vc<ll> B(K);
    FOR(k, K) { B[k] = dist[X[k]]; }
    return B;
  }();

  // 他の駒すべてを n 回ずつターン消費するためにかかるコスト
  vc<ll> COST(N);
  {
    vc<ll> C0(N + 1), C1(N + 1);
    FOR(k, K) {
      ll a = A[k], b = B[k];
      assert(a <= b);
      ll n = b - a;
      chmin(n, N);
      // FOR(x, n) COST[x] += 2 * x + a;
      // FOR(x, n, N) COST[x] += x + b;
      // c1x +c0
      C1[0] += 2, C1[n] -= 2, C0[0] += a, C0[n] -= a;
      C1[n] += 1, C1[N] -= 1, C0[n] += b, C0[N] -= b;
    }
    FOR(n, N) C1[n + 1] += C1[n], C0[n + 1] += C0[n];
    FOR(x, 1, N) COST[x] = C1[x] * x + C0[x];
  }

  auto solution_1 = [&]() -> vc<ll> {
    // K が大きい
    // 再行動回数を枝狩りする
    vc<ll> ANS(N, INF);
    vc<int> V = {X0};

    // min_cnt: v に到達するまでに他のプレイヤがターン消化する最小回数
    vc<ll> min_cnt = bfs(N, G, V, [&](int u, int v) -> int {
      return (S[u] == '1' && u != X0 ? 1 : 0);
    });
    ll LIM = N / K + 1;
    chmin(LIM, count(all(S), '1'));

    // dp[i][v]: v に到達するまでに他のプレイヤが
    // min_cnt[v] + i 回ずつターン消化
    vc<vc<int>> dp(LIM, vc<int>(N, 1e9));
    vc<int> min_cnt_now(N, N);
    deque<pair<int, int>> que;
    dp[0][X0] = 0, que.emplace_back(0, X0);
    while (len(que)) {
      auto [k, v] = POP(que);
      for (int w: G[v]) {
        int k1 = k + (S[v] == '1' && v != X0 ? 1 : 0);
        int x = dp[k - min_cnt[v]][v];
        // 最適になりえないパターンを枝狩りする
        if (!chmin(min_cnt_now[w], k1)) continue;
        if (k1 - min_cnt[w] >= LIM) continue;
        if (N <= x + 1 + ll(K) * (k1 - min_cnt[w])) continue;
        if (chmin(dp[k1 - min_cnt[w]][w], x + 1)) { que.emplace_back(k1, w); }
      }
    }
    FOR(k, LIM) {
      FOR(v, N) {
        ll x = dp[k][v];
        ll n = min_cnt[v] + k;
        if (n < N) chmin(ANS[v], x + COST[n]);
      }
    }
    return ANS;
  };

  auto solution_2 = [&]() -> vc<ll> {
    // 直線の種類ごとに解く
    vc<ll> ANS(N, INF);
    vc<vc<ll>> dp(2, vc<ll>(N, INF));
    vc<pair<int, int>> que1(N + N), que2(N + N);
    auto solve_ab = [&](ll a, ll b) -> void {
      // 他のプレイヤが n 回ターン消化するときに an+b のコストがかかるとして解く
      // v!=X0 かつ S[v]=='1' から出るときにコスト発生
      // dp[v] := プレイヤ1の回数 + an
      fill(all(dp[0]), INF), fill(all(dp[1]), INF);
      int l1 = 0, r1 = 0, l2 = 0, r2 = 0;
      dp[0][X0] = 0, que1[r1++] = {0, X0};
      while (l1 < r1 || l2 < r2) {
        auto [t, v] = [&]() -> pair<int, int> {
          if (l1 == r1) return que2[l2++];
          if (l2 == r2) return que1[l1++];
          auto [t1, v1] = que1[l1];
          auto [t2, v2] = que2[l2];
          return (dp[t1][v1] < dp[t2][v2] ? que1[l1++] : que2[l2++]);
        }();
        for (auto w: G[v]) {
          if (v == X0 || S[v] == '0') {
            if (chmin(dp[t][w], dp[t][v] + 1)) que1[r1++] = {t, w};
          } else {
            if (chmin(dp[1][w], dp[t][v] + a + 1)) que2[r2++] = {1, w};
          }
        }
      }
      FOR(v, N) {
        chmin(ANS[v], dp[0][v]);
        chmin(ANS[v], dp[1][v] + b);
      }
    };

    int L = 1;
    while (L < N) {
      // COST[L], ..., COST[R-1] 部分をまとめて計算する
      int R = L + 2;
      while (R < N && 2 * COST[R - 1] == COST[R - 2] + COST[R]) { ++R; }
      chmin(R, N);
      if (R == L + 1) {
        solve_ab(0, COST[L]);
      } else {
        ll a = COST[L + 1] - COST[L];
        ll b = COST[L] - a * L;
        solve_ab(a, b);
      }
      L = R;
    }
    return ANS;
  };

  vc<ll> ANS = (K >= 200 ? solution_1() : solution_2());
  out(ANS);
}

signed main() {
  solve();
  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