Submission #1267758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267758		Sofiatpc	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	2093 ms	2116 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
const int MAXN = 2*1e3+5, MAXM = 2*1e3+5;
vector<int> l[MAXN];
int a[MAXM], b[MAXM], dist[MAXN][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++) l[j].push_back(i);
        }else{
            for(int j = a[i]; j >= max(a[i]-k+1, b[i]+1); j--) l[j].push_back(i);
        }
    }

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

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)dist[i][j] = -1;

        deque<pair<int,int>> q; 
        for(int x : l[s]){
            dist[s][x] = 1;
            q.push_back({s,x});
        }

        int ans = -1;
        while(!q.empty()){
            int i = q.front().fi, x = q.front().sc; q.pop_front();
            
            if(a[x] < b[x]){
                for(int j = i+1; j <= b[x]; j++){
                    if(j == t){
                        if(ans == -1)ans = dist[i][x];
                        else ans = min(ans,dist[i][x]);
                    }

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

                    for(int linha : l[j]){
                        if(dist[j][linha] != -1)continue;
                        if(linha == x){
                            dist[j][linha] = dist[i][x];
                            q.push_front({j,linha});
                        }else{
                            dist[j][linha] = dist[i][x]+1;
                            q.push_back({j,linha});
                        }
                    }
                }
            }
        }

        cout<<ans<<"\n";
    }

}

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