oj.uz

Submission #595421

# Submission time Handle Problem Language Result Execution time Memory
595421 2022-07-13T17:41:37 Z Hacv16 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 77416 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

#define pb push_back
#define sz(x) (int) x.size()
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define dbg(x) cout << #x << ": " << "[ " << x << " ]\n"

int n, q, h[MAX];
vector<int> adj[MAX];

struct event{
	int s, e;
} ev[MAX];

bool f(event a, event b){ //can i do a --> b ?
	return b.s <= a.e && a.e <= b.e;
}

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

    cin >> n >> q;
    
    for(int i = 1; i <= n; i++){
    	cin >> ev[i].s >> ev[i].e;
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			
			if(f(ev[i], ev[j])) adj[i].pb(j);
		}
	}
	
	while(q--){
		int s, e; cin >> s >> e;
		
		queue<int> q;
		vector<int> dist(n + 1, -1);
		
		q.push(s); dist[s] = 0;
		
		while(q.size()){
			int u = q.front();
			q.pop();
			
			for(auto v : adj[u]){
				if(dist[v] == -1){
					dist[v] = dist[u] + 1;
					q.push(v);
				}
			}
		}
		
		if(dist[e] == -1) cout << "impossible" << '\n';
		else cout << dist[e] << '\n';
	}
	
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Execution timed out 1576 ms 50308 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47280 KB Output is correct
2 Correct 25 ms 47192 KB Output is correct
3 Correct 35 ms 47312 KB Output is correct
4 Correct 35 ms 47304 KB Output is correct
5 Correct 36 ms 47300 KB Output is correct
6 Correct 35 ms 48076 KB Output is correct
7 Correct 41 ms 48936 KB Output is correct
8 Correct 41 ms 49988 KB Output is correct
9 Correct 105 ms 51332 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47280 KB Output is correct
2 Correct 25 ms 47192 KB Output is correct
3 Correct 35 ms 47312 KB Output is correct
4 Correct 35 ms 47304 KB Output is correct
5 Correct 36 ms 47300 KB Output is correct
6 Correct 35 ms 48076 KB Output is correct
7 Correct 41 ms 48936 KB Output is correct
8 Correct 41 ms 49988 KB Output is correct
9 Correct 105 ms 51332 KB Output is correct
10 Correct 26 ms 47188 KB Output is correct
11 Correct 26 ms 47164 KB Output is correct
12 Correct 30 ms 47328 KB Output is correct
13 Correct 27 ms 47284 KB Output is correct
14 Correct 30 ms 47252 KB Output is correct
15 Correct 30 ms 48144 KB Output is correct
16 Correct 39 ms 48940 KB Output is correct
17 Correct 44 ms 49920 KB Output is correct
18 Correct 103 ms 51276 KB Output is correct
19 Execution timed out 1576 ms 77416 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47280 KB Output is correct
2 Correct 25 ms 47192 KB Output is correct
3 Correct 35 ms 47312 KB Output is correct
4 Correct 35 ms 47304 KB Output is correct
5 Correct 36 ms 47300 KB Output is correct
6 Correct 35 ms 48076 KB Output is correct
7 Correct 41 ms 48936 KB Output is correct
8 Correct 41 ms 49988 KB Output is correct
9 Correct 105 ms 51332 KB Output is correct
10 Correct 22 ms 47188 KB Output is correct
11 Correct 29 ms 47188 KB Output is correct
12 Correct 30 ms 47316 KB Output is correct
13 Correct 29 ms 47352 KB Output is correct
14 Correct 30 ms 47236 KB Output is correct
15 Correct 35 ms 48084 KB Output is correct
16 Correct 44 ms 48940 KB Output is correct
17 Correct 41 ms 49972 KB Output is correct
18 Correct 101 ms 51332 KB Output is correct
19 Execution timed out 1583 ms 50088 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 1593 ms 50208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Execution timed out 1576 ms 50308 KB Time limit exceeded
3 Halted 0 ms 0 KB -