結果

問題 No.3351 Towering Tower
コンテスト
ユーザー Nzt3
提出日時 2025-10-29 16:47:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 313 ms / 3,000 ms
コード長 4,887 bytes
コンパイル時間 3,350 ms
コンパイル使用メモリ 302,048 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-13 21:04:06
合計ジャッジ時間 8,770 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;
}

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;
  vector<vl> nmax(N + 1), nmin(N + 1);
  rep(i, 0, N + 1) {
    nmax[i].resize(ssize(G[i]));
    nmin[i].resize(ssize(G[i]));
  }
  while (ans - ng > 1) {
    ll mid = (ans + ng) / 2;
    H[N] = mid;
    rep(from, 0, N) {
      rep(i, 0, ssize(G[from])) {
        int to = G[from][i];
        if (H[to] == H[from]) {
          if (H[from] <= mid) {
            nmax[from][i] = LINF; // inf
            nmin[from][i] = -100;
          } else {
            nmax[from][i] = -100; // NG
            nmin[from][i] = LINF; // NG
          }
        } else if (H[to] > H[from]) {
          if (H[from] <= mid) {
            nmax[from][i] = LINF;
            nmin[from][i] = -100;
          } else {
            nmax[from][i] = LINF;
            nmin[from][i] =
                ((H[from] - mid + (H[to] - H[from] - 1)) / (H[to] - H[from]));
          }
        } else {
          if (H[from] < mid) {
            nmax[from][i] = (H[from] - mid) / (H[to] - H[from]);
            nmin[from][i] = -100;
          } else {
            nmax[from][i] = -100;
            nmin[from][i] = 0;
          }
        }
      }
    }
    rep(i, 0, ssize(G[N])) {
      nmax[N][i] = LINF;
      nmin[N][i] = -100;
    }

    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);
        ll nl = nmin[v][i], nr = nmax[v][i];
        if (dist[vs] >= nl && dist[vs] <= nr && dist[to] == -1) {
          dist[to] = dist[vs] + 1;
          bfs.push(to);
        }
      }
    }
    // rep(i, 0, N + 1) {
    //   rep(j, 0, ssize(G[i])) {
    //     cerr << i << " -> " << G[i][j] << ":" << nmax[i][j] << ',' <<
    //     nmin[i][j]
    //          << endl;
    //   }
    // }

    // rep(i, 0, N + 1) cerr << dist[i] << ' ';
    // cerr << endl;
    // rep(i, N + 1, 2 * (N + 1)) cerr << dist[i] << ' ';
    // cerr << endl;
    // cerr << endl;

    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);
        if (nmax[v][i] >= dist[vs] && nmin[v][i] <= dist[vs] &&
            H[G[v][i]] <= H[v]) {
          if (c) {
            // 奇数回
            chmax(mdist[vs], nmax[v][i] - 1 + nmax[v][i] % 2 + 2);
            chmax(mdist[to], nmax[v][i] - 1 + nmax[v][i] % 2 + 1);
          } else {
            chmax(mdist[vs], nmax[v][i] - nmax[v][i] % 2 + 2);
            chmax(mdist[to], nmax[v][i] - nmax[v][i] % 2 + 1);
          }
        }
      }
    }
    // rep(i, 0, N + 1) cerr << mdist[i] << ' ';
    // cerr << endl;
    // rep(i, N + 1, 2 * (N + 1)) cerr << mdist[i] << ' ';
    // cerr << endl;
    // cerr << endl;
    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);
          if (nmax[v][i] >= mdist[vs] && nmin[v][i] <= mdist[vs]) {
            chmax(mdist[to], mdist[vs] + 1);
            chmin(mdist[to], LINF);
          }
        }
      }
    }
    // cerr << "X=" << mid << endl;
    // rep(i, 0, N + 1) cerr << dist[i] << ' ';
    // cerr << endl;
    // rep(i, N + 1, 2 * (N + 1)) cerr << dist[i] << ' ';
    // cerr << endl;
    // cerr << endl;
    // rep(i, 0, N + 1) cerr << mdist[i] << ' ';
    // cerr << endl;
    // rep(i, N + 1, 2 * (N + 1)) cerr << mdist[i] << ' ';
    // cerr << endl;
    // cerr << endl;
    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