oj.uz

Submission #573095

# Submission time Handle Problem Language Result Execution time Memory
573095 2022-06-05T18:47:22 Z StrawHatWess Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 131560 KB 
#include <bits/stdc++.h>
using namespace std;

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);  

vi adj[MX]; 

int main(){
	IO(); 

	cin>>N>>Q; 

	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 2 ms 3412 KB Output is correct
2 Execution timed out 1593 ms 4804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 17 ms 7452 KB Output is correct
4 Correct 13 ms 7380 KB Output is correct
5 Correct 18 ms 7436 KB Output is correct
6 Correct 58 ms 8148 KB Output is correct
7 Correct 165 ms 9020 KB Output is correct
8 Correct 194 ms 10080 KB Output is correct
9 Correct 1062 ms 11428 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 17 ms 7452 KB Output is correct
4 Correct 13 ms 7380 KB Output is correct
5 Correct 18 ms 7436 KB Output is correct
6 Correct 58 ms 8148 KB Output is correct
7 Correct 165 ms 9020 KB Output is correct
8 Correct 194 ms 10080 KB Output is correct
9 Correct 1062 ms 11428 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 17 ms 7428 KB Output is correct
13 Correct 14 ms 7452 KB Output is correct
14 Correct 18 ms 7380 KB Output is correct
15 Correct 57 ms 8148 KB Output is correct
16 Correct 168 ms 9020 KB Output is correct
17 Correct 213 ms 10080 KB Output is correct
18 Correct 1061 ms 11424 KB Output is correct
19 Execution timed out 1600 ms 131560 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 17 ms 7452 KB Output is correct
4 Correct 13 ms 7380 KB Output is correct
5 Correct 18 ms 7436 KB Output is correct
6 Correct 58 ms 8148 KB Output is correct
7 Correct 165 ms 9020 KB Output is correct
8 Correct 194 ms 10080 KB Output is correct
9 Correct 1062 ms 11428 KB Output is correct
10 Correct 1 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 17 ms 7452 KB Output is correct
13 Correct 13 ms 7428 KB Output is correct
14 Correct 18 ms 7380 KB Output is correct
15 Correct 57 ms 8148 KB Output is correct
16 Correct 168 ms 9020 KB Output is correct
17 Correct 204 ms 10076 KB Output is correct
18 Correct 1077 ms 11436 KB Output is correct
19 Execution timed out 1582 ms 4984 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 1573 ms 4848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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