結果

問題 No.5025 Forest Fire
コンテスト
ユーザー occhan
提出日時 2026-10-24 17:00:35
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,833 ms / 2,000 ms
+ 842µs
コード長 6,556 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,099 ms
コンパイル使用メモリ 366,920 KB
実行使用メモリ 9,932 KB
スコア 173,253,893
最終ジャッジ日時 2026-10-24 17:03:58
合計ジャッジ時間 154,445 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / <nil>
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

static constexpr int MAXN = 50;
static constexpr int MAXV = MAXN * MAXN;
static constexpr int SAMPLES = 90;
static constexpr int CUT_STEPS = 230;
static constexpr int RESTORE_STEPS = 130;

int N, K, V;
vector<string> d;
vector<int> trees;

static unsigned char dry[SAMPLES][MAXV];
static unsigned char cutCell[MAXV];

static int ord_[MAXV], low_[MAXV], sub_[MAXV], parent_[MAXV];
static int sepSize_[MAXV], compId_[MAXV], compSize_[MAXV];
static long long sepSq_[MAXV];
static long long totalValue[MAXV];

static int timer_, compCnt_;

static int deg_[MAXV];
static int nbr_[MAXV][4];

static int ufParent[MAXV], ufSize[MAXV];
static long long restoreValue[MAXV];

inline int getD(int v) {
  return d[v / N][v % N] - '0';
}

void dfsLow(int v, int s, int cid) {
  ord_[v] = low_[v] = timer_++;
  sub_[v] = 1;
  compId_[v] = cid;

  for (int z = 0; z < deg_[v]; ++z) {
    int to = nbr_[v][z];

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

    if (ord_[to] == -1) {
      parent_[to] = v;

      dfsLow(to, s, cid);

      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]);
    }
  }
}

inline void addCutValuesForSample(int s) {
  fill(ord_, ord_ + V, -1);
  fill(parent_, parent_ + V, -1);
  fill(sepSize_, sepSize_ + V, 0);
  fill(sepSq_, sepSq_ + V, 0LL);

  timer_ = 0;
  compCnt_ = 0;

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

    int cid = compCnt_++;

    dfsLow(start, s, cid);

    compSize_[cid] = sub_[start];
  }

  for (int v : trees) {
    if (cutCell[v]) continue;
    if (ord_[v] == -1) continue;

    int S = compSize_[compId_[v]];

    int remain =
        S - 1 - sepSize_[v];

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

    totalValue[v] +=
        1LL * S * S - after;
  }
}

inline int ufFind(int x) {
  while (ufParent[x] != x) {
    ufParent[x] =
        ufParent[ufParent[x]];

    x = ufParent[x];
  }

  return x;
}

inline void ufUnite(int a, int b) {
  a = ufFind(a);
  b = ufFind(b);

  if (a == b) return;

  if (ufSize[a] < ufSize[b]) {
    swap(a, b);
  }

  ufParent[b] = a;
  ufSize[a] += ufSize[b];
}

inline void addRestoreValuesForSample(int s) {
  for (int v : trees) {
    if (!cutCell[v] && dry[s][v]) {
      ufParent[v] = v;
      ufSize[v] = 1;
    } else {
      ufParent[v] = -1;
      ufSize[v] = 0;
    }
  }

  for (int v : trees) {
    if (ufParent[v] == -1) continue;

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

    if (r + 1 < N) {
      int to = v + N;

      if (ufParent[to] != -1) {
        ufUnite(v, to);
      }
    }

    if (c + 1 < N) {
      int to = v + 1;

      if (ufParent[to] != -1) {
        ufUnite(v, to);
      }
    }
  }

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

    int roots[4];
    int rootCount = 0;

    long long mergedSize = 1;
    long long before = 0;

    for (int z = 0; z < deg_[v]; ++z) {
      int to = nbr_[v][z];

      if (ufParent[to] == -1) continue;

      int root = ufFind(to);

      bool duplicate = false;

      for (int k = 0; k < rootCount; ++k) {
        if (roots[k] == root) {
          duplicate = true;
          break;
        }
      }

      if (duplicate) continue;

      roots[rootCount++] = root;

      long long sz = ufSize[root];

      mergedSize += sz;
      before += sz * sz;
    }

    long long after =
        mergedSize * mergedSize;

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

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

  cin >> N >> K;

  V = N * N;

  d.resize(N);

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

  trees.reserve(V);

  for (int r = 0; r < N; ++r) {
    for (int c = 0; c < N; ++c) {
      int v = r * N + c;

      if (d[r][c] != '0') {
        trees.push_back(v);
      }

      if (r > 0) {
        nbr_[v][deg_[v]++] = v - N;
      }

      if (r + 1 < N) {
        nbr_[v][deg_[v]++] = v + N;
      }

      if (c > 0) {
        nbr_[v][deg_[v]++] = v - 1;
      }

      if (c + 1 < N) {
        nbr_[v][deg_[v]++] = v + 1;
      }
    }
  }

  mt19937 rng(123456789);

  for (int s = 0; s < SAMPLES; ++s) {
    for (int v : trees) {
      dry[s][v] =
          ((int)(rng() % 10) < getD(v));
    }
  }

  vector<int> cutList;
  cutList.reserve(CUT_STEPS);

  for (int step = 0;
       step < CUT_STEPS &&
       step < (int)trees.size();
       ++step) {

    fill(
        totalValue,
        totalValue + V,
        0LL);

    for (int s = 0;
         s < SAMPLES;
         ++s) {

      addCutValuesForSample(s);
    }

    int best = -1;

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

      if (best == -1 ||
          totalValue[v] > totalValue[best] ||
          (
              totalValue[v] ==
                  totalValue[best] &&
              (
                  getD(v) > getD(best) ||
                  (
                      getD(v) ==
                          getD(best) &&
                      v < best)))) {

        best = v;
      }
    }

    if (best == -1) break;

    cutCell[best] = 1;
    cutList.push_back(best);
  }

  int restoreSteps =
      min(
          RESTORE_STEPS,
          max(
              0,
              (int)cutList.size() - K));

  for (int step = 0;
       step < restoreSteps;
       ++step) {

    fill(
        restoreValue,
        restoreValue + V,
        0LL);

    for (int s = 0;
         s < SAMPLES;
         ++s) {

      addRestoreValuesForSample(s);
    }

    int best = -1;

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

      if (best == -1 ||
          restoreValue[v] <
              restoreValue[best] ||
          (
              restoreValue[v] ==
                  restoreValue[best] &&
              (
                  getD(v) < getD(best) ||
                  (
                      getD(v) ==
                          getD(best) &&
                      v < best)))) {

        best = v;
      }
    }

    if (best == -1) break;

    cutCell[best] = 0;
  }

  vector<int> answer;

  answer.reserve(K);

  for (int v : trees) {
    if (cutCell[v]) {
      answer.push_back(v);
    }
  }

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

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

  return 0;
}
0