제출 #1267772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267772		Sofiatpc	Railway Trip 2 (JOI22_ho_t4)	C++20	16 / 100	2096 ms	3832 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;}

        queue<pair<int,int>> q; 
        q.push({0,s}); q.push({1,s});

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

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

                    if(dist[0][j] == -1 && l[0][j] != l[0][i]){
                        dist[0][j] = dist[0][i]+1;
                        q.push({0,j});
                    }
                    if(dist[1][j] == -1){
                        dist[1][j] = dist[0][i]+1;
                        q.push({1,j});
                    }
                }
            }else{
               for(int j = i-1; j >= b[l[1][i]]; j--){
                    if(j == t){
                        ans = dist[1][i];
                        break;
                    }

                    if(dist[1][j] == -1 && l[1][j] != l[1][i]){
                        dist[1][j] = dist[1][i]+1;
                        q.push({1,j});
                    }
                    if(dist[0][j] == -1){
                        dist[0][j] = dist[1][i]+1;
                        q.push({0,j});
                    }
                } 
            }
            if(ans != -1)break;
        }

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