結果

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

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,a,b) for(ll i = a; i < (b); i++)

void solve() {
    ll n,m;
    cin >> n >> m;
    vector<ll> h(n+1);
    rep(i,0,n) cin >> h[i];
    vector<vector<ll>> g(n+1);
    rep(i,0,m){
        ll u,v;
        cin >> u >> v;
        u--,v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    ll ok = 3'000'000'000'000, ng = -1;
    while(ok - ng > 1) {
        ll mid = (ok + ng) / 2;
        const ll INF = 1'000'000'000'000'000'000;
        h[n] = mid;

        vector<ll> dist(n*2+2, INF);
        dist[n] = 0;
        using pl = pair<ll,ll>;
        priority_queue<pl, vector<pl>, greater<pl>> q;
        q.push({0,n});

        while(q.size()) {
            auto [cst, nw] = q.top(); q.pop();
            if(cst != dist[nw]) continue;

            ll odd = (nw / (n+1));
            ll pos = nw % (n+1);

            for(auto to: g[pos]) {
                if(to == n) continue;
                ll to_idx = to + (odd ^ 1)*(n+1);

                if (h[n] >= (h[pos] - h[to]) * dist[nw] + h[pos]) {
                    if(dist[to_idx] > dist[nw]+1){
                        dist[to_idx] = dist[nw]+1;
                        q.push({dist[to_idx], to_idx});
                    }
                }
            }
        }

        vector<ll> mdist(n, -INF);
        rep(i,0,n) {
            if (dist[i] != INF) {
                mdist[i] = max(mdist[i], dist[i]);
            }
            if (dist[i + n+1] != INF) {
                mdist[i] = max(mdist[i], dist[i + n+1]);
            }
            for(auto to: g[i]) {
                if(to == n) continue;
                if(h[i] > h[n] || h[to] > h[n]) continue;
                ll x;
                if(h[i] > h[to]) {
                    x = (h[n] - h[i]) / (h[i] - h[to]);
                    if(h[n] - h[i] < 0 && (h[i] - h[to]) % (h[i] - h[to])) x--;
                }else{
                    x = INF;
                }

                ll y;
                if(h[to] > h[i]) {
                    y = (h[n] - h[to]) / (h[to] - h[i]);
                    if(h[n] - h[to] < 0 && (h[to] - h[i]) % (h[to] - h[i])) y--;
                }else{
                    y = INF;
                }

                if(dist[i] != INF) {
                    mdist[i] = max({mdist[i], min((x/2*2) +2, ((y+1)/2*2)-1 + 1)});
                }
                if(dist[i + n+1] != INF) {
                    mdist[i] = max({mdist[i], min(((x+1)/2*2-1)+2, (y/2*2)+1)});
                }
            }

            mdist[i] = min(mdist[i], 2'000'000'000LL);
        } 

        vector<int> iot(n);
        iota(iot.begin(), iot.end(), 0);
        sort(iot.begin(), iot.end(), [&](int a, int b) {
            return h[a] < h[b];
        });

        for(auto i: iot) {
            if(mdist[i] == -INF) continue;
            for(auto to: g[i]) {
                if(to == n) continue;
                if (h[n] >= (h[i] - h[to]) * mdist[i] + h[i]) {
                    if(mdist[to] < mdist[i]+1){
                        mdist[to] = mdist[i]+1;
                    }
                }
            }
        }

        bool ex = false;
        rep(i,0,n) {
            if(mdist[i] == -INF) ex = true;
        }
        if(ex) ng = mid;
        else ok = mid;

    }

    cout << ok << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}
0