제출 #1333197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1333197		Luvidi	Railway Trip 2 (JOI22_ho_t4)	C++20	27 / 100	2095 ms	10420 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

void solve() {
    int n,k;
    cin>>n>>k;
    int m;
    cin>>m;
    pii a[m];
    for(int i=0;i<m;i++)cin>>a[i].fs>>a[i].sc;
    int q;
    cin>>q;
    while(q--){
        int s,t;
        cin>>s>>t;
        int ds[n+1];
        memset(ds,63,sizeof(ds));
        ds[s]=0;
        queue<pii> q;
        vector<int> v[n+1];
        for(auto[x,y]:a){
            if(x<y){
                if(x<=s&&s<=min(y,x+k-1)){
                    q.push({s,y});
                }else{
                    v[x].pb(y);
                    v[min(y,x+k-1)].pb(y);
                }
            }else{
                if(max(y,x-k+1)<=s&&s<=x){
                    q.push({s,y});
                }else{
                    v[x].pb(y);
                    v[max(y,x-k+1)].pb(y);
                }
            }
        }
        int l=s,r=s;
        while(!q.empty()){
            auto[x,y]=q.front();
            q.pop();
            while(l>y){
                ds[--l]=ds[x]+1;
                for(int z:v[l])q.push({l,z});
            }
            while(r<y){
                ds[++r]=ds[x]+1;
                for(int z:v[r])q.push({r,z});
            }
        }
        int ans=ds[t];
        if(ans>1e9)ans=-1;
        cout<<ans<<'\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13