oj.uz

Submission #573096

# Submission time Handle Problem Language Result Execution time Memory
573096 2022-06-05T18:50:36 Z StrawHatWess Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 129100 KB 
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef vector<int>vi; 
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF=2e9;
const int MX=1e5+10; 



void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////


int N,Q; 
vi L(MX), R(MX);  


int main(){
	boost; 
	IO(); 

	cin>>N>>Q; 

	vi L(N+1), R(N+1), adj[N+1]; 
	FOR(i,1,N+1) cin>>L[i]>>R[i]; 

	
	FOR(i,1,N+1) FOR(j,1,N+1) if(i!=j){
		if(R[i]>=L[j] && R[i]<=R[j]) adj[i].pb(j); 
	}


	vector<vi> dist(N+1, vi(N+1,INF)); 

	FOR(s,1,N+1){
		dist[s][s]=0; 

		queue<int>q; 
		q.push(s); 

		while(sz(q)){
			int u=q.front(); 
			q.pop(); 

			for(int v: adj[u]) if(dist[s][v]==INF){
				dist[s][v]=dist[s][u]+1; 
				q.push(v); 
			}
		}
	}	


	while(Q--){
		int s,e; cin>>s>>e; 

		if(dist[s][e]==INF) cout << "impossible" << endl;
		else cout << dist[s][e] << endl; 
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Execution timed out 1581 ms 4516 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 15 ms 5140 KB Output is correct
4 Correct 12 ms 5136 KB Output is correct
5 Correct 17 ms 5076 KB Output is correct
6 Correct 59 ms 5844 KB Output is correct
7 Correct 163 ms 6708 KB Output is correct
8 Correct 196 ms 7756 KB Output is correct
9 Correct 1071 ms 9116 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 15 ms 5140 KB Output is correct
4 Correct 12 ms 5136 KB Output is correct
5 Correct 17 ms 5076 KB Output is correct
6 Correct 59 ms 5844 KB Output is correct
7 Correct 163 ms 6708 KB Output is correct
8 Correct 196 ms 7756 KB Output is correct
9 Correct 1071 ms 9116 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct
11 Correct 1 ms 1108 KB Output is correct
12 Correct 16 ms 5132 KB Output is correct
13 Correct 11 ms 5076 KB Output is correct
14 Correct 16 ms 5136 KB Output is correct
15 Correct 58 ms 5904 KB Output is correct
16 Correct 163 ms 6708 KB Output is correct
17 Correct 204 ms 7764 KB Output is correct
18 Correct 1067 ms 9108 KB Output is correct
19 Execution timed out 1590 ms 129100 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 15 ms 5140 KB Output is correct
4 Correct 12 ms 5136 KB Output is correct
5 Correct 17 ms 5076 KB Output is correct
6 Correct 59 ms 5844 KB Output is correct
7 Correct 163 ms 6708 KB Output is correct
8 Correct 196 ms 7756 KB Output is correct
9 Correct 1071 ms 9116 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct
11 Correct 1 ms 1108 KB Output is correct
12 Correct 15 ms 5140 KB Output is correct
13 Correct 11 ms 5076 KB Output is correct
14 Correct 17 ms 5132 KB Output is correct
15 Correct 54 ms 5908 KB Output is correct
16 Correct 160 ms 6676 KB Output is correct
17 Correct 196 ms 7764 KB Output is correct
18 Correct 1066 ms 9164 KB Output is correct
19 Execution timed out 1584 ms 4564 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Execution timed out 1581 ms 4516 KB Time limit exceeded
3 Halted 0 ms 0 KB -