oj.uz

Submission #959453

# Submission time Handle Problem Language Result Execution time Memory
959453 2024-04-08T08:41:26 Z happy_node Railway Trip 2 (JOI22_ho_t4) C++17
0 / 100
 2000 ms 4692 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2804 KB Output is correct
2 Correct 68 ms 2908 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 300 ms 2812 KB Output is correct
5 Correct 58 ms 2652 KB Output is correct
6 Execution timed out 2037 ms 2652 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2804 KB Output is correct
2 Correct 68 ms 2908 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 300 ms 2812 KB Output is correct
5 Correct 58 ms 2652 KB Output is correct
6 Execution timed out 2037 ms 2652 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 3928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 4188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 4692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2804 KB Output is correct
2 Correct 68 ms 2908 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 300 ms 2812 KB Output is correct
5 Correct 58 ms 2652 KB Output is correct
6 Execution timed out 2037 ms 2652 KB Time limit exceeded
7 Halted 0 ms 0 KB -