Submission #997648

#	Time	Username	Problem	Language	Result	Execution time	Memory
997648		Otalp	Railway Trip 2 (JOI22_ho_t4)	C++14	8 / 100	2067 ms	10024 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second
#define ld long double
#define pb push_back

pii a[200100];
pii c[200100];
int dp[200100], us[200100];



void solve(){
    int n, k;
    cin>>n>>k;
    int m;

    cin>>m;
    for(int i=1; i<=m; i++){
        cin>>a[i].ff>>a[i].ss;
    }
    for(int i=1; i<=n; i++){
        int l=i, r=i;
        for(int j=1; j<=m; j++){
            if(min(a[j].ff, a[j].ss) > i or max(a[j].ff, a[j].ss) < i) continue;
                //cout<<i<<'\n';
            if(a[j].ff > a[j].ss and a[j].ff - k + 1 <= i){
                l = min(l, a[j].ss);
            }
            if(a[j].ff < a[j].ss and a[j].ff + k - 1 >= i){
                r = max(r, a[j].ss);
            }        
        }
        c[i] = {l, r};
    }
    //for(int i=1; i<=n; i++){
        //cout<<c[i].ff<<' '<<c[i].ss<<'\n';
    //}
    int t;
    cin>>t;
    while(t--){
        int s, f;
        cin>>s>>f;
        queue<int> q;
        q.push(s);
        for(int i=1; i<=n; i++){
            dp[i] = us[i] = 0;
        }
        dp[s] = 0;
        us[s] = 1;
        while(q.size()){
            int v = q.front();
            q.pop();
            for(int i = c[v].ff; i<=c[v].ss; i++){
                if(us[i] == 1) continue;
                dp[i] = dp[v] + 1;
                q.push(i);
                us[i] = 1;
            }
        }
        if(us[f] == 0){
            cout<<-1<<'\n';
        }
        else{
            cout<<dp[f]<<'\n';    
        }
    }
}


signed main(){
    solve();
}

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