結果

問題 No.3351 Towering Tower
コンテスト
ユーザー Nzt3
提出日時 2025-11-06 01:04:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 394 ms / 3,000 ms
コード長 3,557 bytes
コンパイル時間 3,306 ms
コンパイル使用メモリ 299,268 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-13 21:12:16
合計ジャッジ時間 9,979 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

#define rep(i, l, r) for (ll i = (l); i < (r); i++)
#define all(v) v.begin(), v.end()

const ll LINF = (1ll << 61) + (1ll << 31) - 1;
template <typename T, typename S> bool chmin(T &a, const S &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S> bool chmax(T &a, const S &b) {
  return a < b ? a = b, 1 : 0;
}

struct _ {
  _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

void solve();

int main() {
  int T = 1;
  cin >> T;
  rep(i, 0, T) solve();
}

void solve() {
  ll N, M;
  cin >> N >> M;
  vl H(N + 1);
  rep(i, 0, N) cin >> H[i];
  vector G(N + 1, vi());
  rep(i, 0, M) {
    int U, V;
    cin >> U >> V;
    --U, --V;
    if (V != N)
      G[U].push_back(V);
    G[V].push_back(U);
  }
  vector<pll> Hord(N);
  rep(i, 0, N) Hord[i] = pii{H[i], i};
  sort(all(Hord));
  ll ans = 1'000'000'000 * N, ng = -1;
  auto nminmax = [&](int from, int to, ll X) -> pll {
    if (from == N)
      return pll{-100, LINF};
    if (H[to] == H[from]) {
      if (H[from] <= X) {
        // OK
        return pll{-100, LINF};
      } else {
        // NG
        return pll{LINF, -100};
      }
    } else if (H[to] > H[from]) {
      if (H[from] <= X) {
        // OK
        return pll{-100, LINF};
      } else {
        return pll{(H[from] - X + (H[to] - H[from] - 1)) / (H[to] - H[from]),
                   LINF};
      }
    } else {
      if (H[from] < X) {
        return pll{-100, (H[from] - X) / (H[to] - H[from])};
      } else {
        return pll{0, -100};
      }
    }
  };
  while (ans - ng > 1) {
    ll mid = (ans + ng) / 2;
    H[N] = mid;

    vl dist((N + 1) * 2, -1);
    queue<int> bfs;
    dist[N] = 0;
    bfs.push(N);
    while (bfs.size()) {
      int vs = bfs.front(), v = vs % (N + 1), c = vs / (N + 1);
      bfs.pop();
      rep(i, 0, ssize(G[v])) {
        int to = G[v][i] + (1 - c) * (N + 1);
        auto [nl, nr] = nminmax(v, G[v][i], mid);
        if (dist[vs] >= nl && dist[vs] <= nr && dist[to] == -1) {
          dist[to] = dist[vs] + 1;
          bfs.push(to);
        }
      }
    }

    vl mdist = dist;
    rep(vs, 0, (N + 1) * 2) {
      if (mdist[vs] == -1)
        continue;
      if (vs % (N + 1) == N)
        continue;
      int v = vs % (N + 1), c = vs / (N + 1);
      rep(i, 0, ssize(G[v])) {
        int to = G[v][i] + (1 - c) * (N + 1);
        auto [nl, nr] = nminmax(v, G[v][i], mid);
        if (nr >= dist[vs] && nl <= dist[vs] && H[G[v][i]] <= H[v]) {
          if (c) {
            chmax(mdist[vs], nr - 1 + nr % 2 + 2);
            chmax(mdist[to], nr - 1 + nr % 2 + 1);
          } else {
            chmax(mdist[vs], nr - nr % 2 + 2);
            chmax(mdist[to], nr - nr % 2 + 1);
          }
        }
      }
    }
    for (auto &i : mdist)
      chmin(i, LINF);
    for (auto [h, v] : Hord) {
      rep(c, 0, 2) {
        int vs = v + c * (N + 1);
        if (mdist[vs] < 0)
          continue;
        rep(i, 0, ssize(G[v])) {
          int to = G[v][i] + (1 - c) * (N + 1);
          auto [nl, nr] = nminmax(v, G[v][i], mid);
          if (nr >= mdist[vs] && nl <= mdist[vs]) {
            chmax(mdist[to], mdist[vs] + 1);
            chmin(mdist[to], LINF);
          }
        }
      }
    }
    bool ok = 1;
    rep(i, 0, N) {
      if (mdist[i] == -1 && mdist[i + (N + 1)] == -1)
        ok = 0;
    }
    if (ok)
      ans = mid;
    else
      ng = mid;
  }

  cout << ans << '\n';
}
0