結果

問題 No.3351 Towering Tower
コンテスト
ユーザー keisuke6
提出日時 2025-11-13 23:39:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,406 bytes
コンパイル時間 2,014 ms
コンパイル使用メモリ 207,032 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-13 23:39:25
合計ジャッジ時間 5,626 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 9 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int TT;
	cin>>TT;
	while(TT--){
	    int N,M;
	    cin>>N>>M;
	    vector<int> A(N);
	    for(int i=0;i<N;i++) cin>>A[i];
	    vector<vector<int>> G(N+1);
	    for(int i=0;i<M;i++){
	        int a,b;
	        cin>>a>>b;
	        a--;
	        b--;
	        G[a].push_back(b);
	        G[b].push_back(a);
	    }
	    int ac = 3e12, wa = -1;
	    while(ac-wa > 1){
	        int md = (ac+wa)/2;
	        int X = md;
	        vector<int> dist(N+1,1e18);
	        dist[N] = 1;
	        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	        pq.push({dist[N],N});
	        while(!pq.empty()){
	            auto [w,u] = pq.top();
	            pq.pop();
	            if(dist[u] != w) continue;
	            for(auto v:G[u])if((w == 1 || (A[u]-X)*w <= (A[v]-X)*(w-1)) && dist[v] > w+1){
	                dist[v] = w+1;
	                pq.push({dist[v],v});
	            }
	        }
	        if(*max_element(dist.begin(),dist.end()) <= 2*N) ac = md;
	        else wa = md;
	    }
	    cout<<ac<<endl;
	}
}
// これだと違うんですね
// 辺って 3 種類あんねん
// ・時刻 t 以降通れる
// ・時刻 t までとおれる
// ・いつでも通れる
// 時刻 t はめちゃでかい値になりうる
0