結果

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

ソースコード

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 (int 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<pii> 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;
            nmin[from][i] = -1;
          } else {
            nmax[from][i] = -1;
            nmin[from][i] = 0;
          }
        } else if (H[to] > H[from]) {
          if (H[from] <= mid) {
            nmax[from][i] = LINF;
            nmin[from][i] = -1;
          } 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] = -1;
          } else {
            nmax[from][i] = -1;
            nmin[from][i] = 0;
          }
        }
      }
    }
    rep(i, 0, ssize(G[N])) {
      nmax[N][i] = LINF;
      nmin[N][i] = 0;
    }

    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), 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);
        }
      }
    }
    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] >= mdist[vs] && nmin[v][i] <= mdist[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);
          }
        }
      }
    }
    for(auto &i:mdist)chmin(i,LINF);
    for (auto [h, v] : Hord) {
      rep(c, 0, 2) {
        int vs = v + c * (N + 1);
        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);
          }
        }
      }
    }
    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