Submission #1041518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041518		irmuun	Railway Trip 2 (JOI22_ho_t4)	C++17	8 / 100	2048 ms	524288 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,k;
    cin>>n>>k;
    bool to[n+5][n+5];
    memset(to,false,sizeof to);
    ll m;
    cin>>m;
    for(ll i=1;i<=m;i++){
        ll a,b;
        cin>>a>>b;
        if(a<b){
            for(ll j=a;j<=min(a+k-1,b-1);j++){
                for(ll l=j+1;l<=b;l++){
                    to[j][l]=true;
                }
            }
        }
        else{
            for(ll j=a;j>=max(a-k+1,b+1);j--){
                for(ll l=j-1;l>=b;l--){
                    to[j][l]=true;
                }
            }
        }
    }
    vector<vector<ll>>ans(n+5,vector<ll>(n+5,1e18));
    for(ll i=1;i<=n;i++){
        set<pair<ll,ll>>st;
        st.insert({0,i});
        ans[i][i]=0;
        while(!st.empty()){
            auto [v,j]=*st.begin();
            st.erase(st.begin());
            if(ans[i][j]!=v) continue;
            for(ll l=1;l<=n;l++){
                if(to[j][l]&&v+1<ans[i][l]){
                    ans[i][l]=v+1;
                    st.insert({v+1,l});
                }
            }
        }
    }
    ll q;
    cin>>q;
    while(q--){
        ll s,t;
        cin>>s>>t;
        if(ans[s][t]==1e18) ans[s][t]=-1;
        cout<<ans[s][t]<<"\n";
    }
}

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