結果

問題 No.2366 登校
ユーザー vjudge1
提出日時 2025-08-14 12:34:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,682 bytes
コンパイル時間 2,415 ms
コンパイル使用メモリ 214,144 KB
実行使用メモリ 822,292 KB
最終ジャッジ日時 2025-08-14 12:35:09
合計ジャッジ時間 13,939 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1 -- * 1
other -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

//E
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


ll n, m, k, t;
vector<ll> C, D;
vector<bool> isTree;
ll Edge;

bool feasible(ll F) {
    //tandain pohon yg bisa dipakai
    vector<char> allow(Edge, 0);
    bool exist = false;
    for(ll i = 0; i<Edge; i++) {
        if(isTree[i] && D[i]<=F) {
            allow[i] = 1;
            if(C[i]>1) {
                exist = true;
            }
        }
    }

    //kl ada pohon dgn C>1, bisa kurangin waktu infinite
    //Jika semua C <= 1 Dijkstra
    vector<ll> dist(Edge, (1LL<<60));
  

    dist[0] = 0;

    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    pq.push({0, 0});

    ll row[4] = {-1, 1, 0, 0};
    ll col[4] = {0, 0, -1, 1};
    ll target = (n-1)*m + (m-1); //mau ngebuat grid 2D >> 1D

    while(!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if(d != dist[u]) continue;
        if(u == target) break;
        
        ll r = u/m, c = u%m;

        //move ke tetangga
        for(ll k = 0; k<4; k++) {
            ll move_r = r+row[k], move_c = c+col[k];
            if(move_r<0||move_r>=n||move_c<0||move_c>=m) continue;
            ll v = move_r * m + move_c;
            ll nd = d+1;

            if(dist[v] > nd) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }

        //cek self loop
        if(allow[u]) {
            ll w = 1-C[u];
            ll nd = d+w;
            if(dist[u] > nd) {
                dist[u] = nd;
                pq.push({nd, u});
            }
        }
    }
    
    if(exist && dist[target] <= t) return true;
    return dist[target] <= t;
   
}




int main() {

    cin>>n>>m>>k>>t;

    Edge = n*m;
    C.assign(Edge, 0);
    D.assign(Edge, LLONG_MAX);
    isTree.assign(Edge, false);

    vector<ll> allD;

    for(ll i = 0; i<k; i++) {
        ll a, b, c, d;
        cin>>a>>b>>c>>d;
        --a; --b; //1 based index

        ll idx = a*m + b; // ubah ke 1D
        isTree[idx] = true;
        C[idx] = c;
        D[idx] = d;
        allD.push_back(d);
    }


    ll dist_min = (n-1)+(m-1);
    if(dist_min <= t){
        cout<<0;
        return 0;
    }
    if(k==0) { //dist_min>t dan k == 0 -> tdk ada pohon
        cout<<-1;
        return 0;
    }

    sort(allD.begin(), allD.end());
    allD.erase(unique(allD.begin(), allD.end()), allD.end());

    
    //BS
    ll l = 0, r = allD.size()-1;
    ll ans = -1;

    while(l<=r) {
        ll mid = (l+r)/2;
        ll val = allD[mid];
        if(feasible(val)) {
            ans = val;
            r = mid-1;
        } 
        else{
            l = mid+1;
        }
    }

    cout<<ans;
    
}
0