#1195018 (C++23(gcc16)) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: occhan
• 提出日時: 2026-10-24 15:58:32
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,679 ms / 2,000 ms
• コード長: 3,648 bytes
• コンパイル時間: 4,307 ms
• コンパイル使用メモリ: 363,796 KB
• 実行使用メモリ: 9,928 KB
• スコア: 146,830,499
• 最終ジャッジ日時: 2026-10-24 16:00:57
• 合計ジャッジ時間: 144,514 ms
• ジャッジサーバーID （参考情報）: judge4_0 / <nil>

ファイルパターン	結果
other	AC * 50

ソースコード

#include <bits/stdc++.h>
using namespace std;

static constexpr int MAXN = 50;
static constexpr int MAXV = MAXN * MAXN;
static constexpr int SAMPLES = 256;

int N, K;
vector<string> d;

bool dry[SAMPLES][MAXV];
bool cutCell[MAXV];

int ord_[MAXV];
int low_[MAXV];
int sub_[MAXV];
int parent_[MAXV];
int sepSize_[MAXV];
long long sepSq_[MAXV];

long long totalValue[MAXV];

int timer_;

void dfs(int v, int s, vector<int>& comp) {
  ord_[v] = low_[v] = timer_++;
  sub_[v] = 1;
  comp.push_back(v);

  int r = v / N;
  int c = v % N;

  static const int dr[4] = {-1, 1, 0, 0};
  static const int dc[4] = {0, 0, -1, 1};

  for (int dir = 0; dir < 4; ++dir) {
    int nr = r + dr[dir];
    int nc = c + dc[dir];

    if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;

    int to = nr * N + nc;

    if (cutCell[to]) continue;
    if (!dry[s][to]) continue;

    if (ord_[to] == -1) {
      parent_[to] = v;
      dfs(to, s, comp);

      sub_[v] += sub_[to];
      low_[v] = min(low_[v], low_[to]);

      if (low_[to] >= ord_[v]) {
        sepSize_[v] += sub_[to];
        sepSq_[v] += 1LL * sub_[to] * sub_[to];
      }
    } else if (to != parent_[v]) {
      low_[v] = min(low_[v], ord_[to]);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> N >> K;

  d.resize(N);
  for (int i = 0; i < N; ++i) cin >> d[i];

  int V = N * N;

  vector<int> trees;
  trees.reserve(V);

  for (int r = 0; r < N; ++r) {
    for (int c = 0; c < N; ++c) {
      if (d[r][c] != '0') {
        trees.push_back(r * N + c);
      }
    }
  }

  mt19937 rng(123456789);

  for (int s = 0; s < SAMPLES; ++s) {
    for (int v = 0; v < V; ++v) {
      int r = v / N;
      int c = v % N;
      int p = d[r][c] - '0';

      if (p == 0) {
        dry[s][v] = false;
      } else {
        dry[s][v] =
            static_cast<int>(rng() % 10) < p;
      }
    }
  }

  vector<int> answer;
  answer.reserve(K);

  for (int step = 0; step < K; ++step) {
    fill(totalValue, totalValue + V, 0LL);

    for (int s = 0; s < SAMPLES; ++s) {
      fill(ord_, ord_ + V, -1);
      fill(parent_, parent_ + V, -1);
      fill(sepSize_, sepSize_ + V, 0);
      fill(sepSq_, sepSq_ + V, 0LL);

      timer_ = 0;

      for (int start : trees) {
        if (cutCell[start]) continue;
        if (!dry[s][start]) continue;
        if (ord_[start] != -1) continue;

        vector<int> comp;
        comp.reserve(256);

        dfs(start, s, comp);

        int S = static_cast<int>(comp.size());
        long long before = 1LL * S * S;

        for (int v : comp) {
          int remain =
              S - 1 - sepSize_[v];

          long long after =
              sepSq_[v] +
              1LL * remain * remain;

          totalValue[v] += before - after;
        }
      }
    }

    int best = -1;

    for (int v : trees) {
      if (cutCell[v]) continue;

      if (best == -1) {
        best = v;
        continue;
      }

      if (totalValue[v] != totalValue[best]) {
        if (totalValue[v] > totalValue[best]) {
          best = v;
        }
        continue;
      }

      int vr = v / N;
      int vc = v % N;
      int br = best / N;
      int bc = best % N;

      int vd = d[vr][vc] - '0';
      int bd = d[br][bc] - '0';

      if (vd != bd) {
        if (vd > bd) best = v;
        continue;
      }

      if (vr != br) {
        if (vr < br) best = v;
        continue;
      }

      if (vc < bc) best = v;
    }

    if (best == -1) break;

    cutCell[best] = true;
    answer.push_back(best);
  }

  cout << answer.size() << '\n';

  for (int v : answer) {
    cout << v / N << ' ' << v % N << '\n';
  }

  return 0;
}