Submission #959453

#	Time	Username	Problem	Language	Result	Execution time	Memory
959453		happy_node	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	2049 ms	4692 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=1e5+5;

int N,K,M,Q;
vector<int> adj[MX];
int dist[MX], par[MX];
int A[MX], B[MX];

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

	cin>>N>>K>>M;

	for(int i=1;i<=M;i++) cin>>A[i]>>B[i];

        cin>>Q;

        for(int i=1;i<=Q;i++) {
        	int s, t;
        	cin>>s>>t;

        	queue<int> q;
        	for(int i=1;i<=N;i++) dist[i]=-1;

        	dist[s]=0;
       		q.push(s);

        	while(!q.empty()) {
        		int p=q.front(); q.pop();

        		for(int i=1;i<=M;i++) {
        			if(A[i]<B[i]) {
        				int m=min(A[i]+K-1,B[i]-1);
        				if(A[i]<=p&&p<=m) {
        					for(int j=p;j<=B[i];j++) 
        						if(dist[j]==-1) {
        							par[j]=p;
        							dist[j]=dist[p]+1;
        							q.push(j);
        						}
        				}
        			} else {
        				int m=max(A[i]-K+1,B[i]+1);
        				if(m<=p&&p<=A[i]) {
        					for(int j=B[i];j<=p;j++) 
        						if(dist[j]==-1) {
        							par[j]=p;
        							dist[j]=dist[p]+1;
        							q.push(j);
        						}
        				}
        			}
        		}
        	}

        	cout<<dist[t]<<'\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