Submission #1016286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016286		Aiperiii	Railway Trip 2 (JOI22_ho_t4)	C++14	16 / 100	1994 ms	604 KiB

Main

#include <bits/stdc++.h>
//#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=2005;
vector <int> g[N];
int L[N],R[N];
queue <int> q;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    int m;
    cin>>m;
    for(int i=1;i<=n;i++){
        L[i]=i;R[i]=i;
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        if(a<b){
            for(int j=a;j<=min(b-1,a+k-1);j++){
                R[j]=max(R[j],b);
            }
        }
        else{
            for(int j=a;j>=max(b+1,a-k+1);j--){
                L[j]=min(L[j],b);
            }
            
        }
    }
    int Q;
    cin>>Q;
    while(Q--){
        int s,t;
        cin>>s>>t;
        vector <int> d(n+1,-1),vis(n+1);
        d[s]=0;
        q.push(s);
        vis[s]=1;
        while(!q.empty()){
            int v=q.front();
            q.pop();
            int mn=1e9,mx=0;
            int mxr=-1,mnl=-1;
            for(int i=L[v];i<=R[v];i++){
                if(d[i]==-1)d[i]=d[v]+1;
                if(L[i]<mn){
                    mn=L[i];
                    mnl=i;
                }
                if(R[i]>mx){
                    mx=R[i];
                    mxr=i;
                }
            }
            if(!vis[mxr]){
                vis[mxr]=1;
                q.push(mxr);
            }
            if(!vis[mnl]){
                vis[mnl]=1;
                q.push(mnl);
            }
            
        }
        cout<<d[t]<<"\n";
    }
}

/*

*/

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