Submission #1267766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267766		Sofiatpc	Railway Trip 2 (JOI22_ho_t4)	C++20	8 / 100	2096 ms	3668 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
const int MAXN = 1e5+5, MAXM = 2*1e5+5;
int l[2][MAXN], a[MAXM], b[MAXM], dist[2][MAXN];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,k,m; cin>>n>>k>>m;
    for(int i = 1; i <= m; i++){
        cin>>a[i]>>b[i];

        if(a[i] < b[i]){
            for(int j = a[i]; j <= min(a[i]+k-1, b[i]-1); j++)
                if(l[0][j] == 0 || b[l[0][j]] < b[i])l[0][j] = i;
        }else{
            for(int j = a[i]; j >= max(a[i]-k+1, b[i]+1); j--)
                if(l[1][j] == 0 || b[l[1][j]] > b[i])l[1][j] = i;
        }
    }

   

    int q; cin>>q;
    while(q--){
        int s,t; cin>>s>>t;

        dist[0][s] = 1; dist[1][s] = 1;
        for(int i = 1; i <= n; i++)
            if(i != s){dist[0][i] = -1; dist[1][i] = -1;}

        deque<pair<int,int>> q; 
        q.push_back({0,s}); q.push_back({1,s});

        int ans = -1;
        while(!q.empty()){
            int x = q.front().fi, i = q.front().sc; q.pop_front();
            if(l[x][i] == 0)continue;
            

            if(x == 0){
                for(int j = i+1; j <= b[l[0][i]]; j++){
                    if(j == t){
                        if(ans == -1)ans = dist[0][i];
                        else ans = min(ans,dist[0][i]);
                    }

                    if(dist[0][j] == -1){
                        if(l[0][j] == l[0][i]){
                            dist[0][j] = dist[0][i];
                            q.push_front({0,j});
                        }else{
                            dist[0][j] = dist[0][i]+1;
                            q.push_back({0,j});
                        }
                    }
                    if(dist[1][j] == -1){
                        dist[1][j] = dist[0][i]+1;
                        q.push_back({1,j});
                    }
                }
            }else{
               for(int j = i-1; j >= b[l[1][i]]; j--){
                    if(j == t){
                        if(ans == -1)ans = dist[1][i];
                        else ans = min(ans,dist[1][i]);
                    }

                    if(dist[1][j] == -1){
                        if(l[1][j] == l[1][i]){
                            dist[1][j] = dist[1][i];
                            q.push_front({1,j});
                        }else{
                            dist[1][j] = dist[1][i]+1;
                            q.push_back({1,j});
                        }
                    }
                    if(dist[0][j] == -1){
                        dist[0][j] = dist[1][i]+1;
                        q.push_back({0,j});
                    }
                } 
            }
        }

        cout<<ans<<"\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