답안 #701327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701327	2023-02-20T23:09:21 Z	angelo_torres	Event Hopping (BOI22_events)	C++17	10 / 100	1500 ms	32836 KB

events

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

int n,q,s[N],e[N],d[N];
bool o[N];
vector<int> g[N];

void bfs(int v){
	for(int i = 1; i <= n; ++i) d[i] = N, o[i] = 0;
	d[v] = 0;
	queue<int> q;
	q.push(v);
	while(!q.empty()){
		int r = q.front();
		q.pop();
		for(auto u : g[r]){
			if(!o[u]){
				o[u] = 1, d[u] = d[r]+1;
				q.push(u);
			} 
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) cin >> s[i] >> e[i];
	if(n <= 5000){
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= n; ++j){
				if(i == j) continue;
				if(s[j] <= e[i] && e[i] <= e[j]){
					// cout << i << " " << j << "\n";
					g[i].push_back(j);
				}
			}
		}
		while(q--){
			int w,z; cin >> w >> z;
			bfs(w);
			if(d[z] == N){
				cout << "impossible\n";
			}else{
				cout << d[z] << "\n";
			}
		}
	}
	return 0;
}

Subtask #1

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Incorrect	20 ms	5584 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	7 ms	2708 KB	Output is correct
4	Correct	6 ms	2644 KB	Output is correct
5	Correct	7 ms	2748 KB	Output is correct
6	Correct	11 ms	3484 KB	Output is correct
7	Correct	19 ms	4348 KB	Output is correct
8	Correct	19 ms	5408 KB	Output is correct
9	Correct	90 ms	6740 KB	Output is correct

Subtask #3

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	7 ms	2708 KB	Output is correct
4	Correct	6 ms	2644 KB	Output is correct
5	Correct	7 ms	2748 KB	Output is correct
6	Correct	11 ms	3484 KB	Output is correct
7	Correct	19 ms	4348 KB	Output is correct
8	Correct	19 ms	5408 KB	Output is correct
9	Correct	90 ms	6740 KB	Output is correct
10	Correct	3 ms	2680 KB	Output is correct
11	Correct	2 ms	2644 KB	Output is correct
12	Correct	9 ms	2748 KB	Output is correct
13	Correct	6 ms	2644 KB	Output is correct
14	Correct	7 ms	2644 KB	Output is correct
15	Correct	11 ms	3476 KB	Output is correct
16	Correct	25 ms	4312 KB	Output is correct
17	Correct	26 ms	5332 KB	Output is correct
18	Correct	84 ms	6740 KB	Output is correct
19	Execution timed out	1572 ms	32836 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	7 ms	2708 KB	Output is correct
4	Correct	6 ms	2644 KB	Output is correct
5	Correct	7 ms	2748 KB	Output is correct
6	Correct	11 ms	3484 KB	Output is correct
7	Correct	19 ms	4348 KB	Output is correct
8	Correct	19 ms	5408 KB	Output is correct
9	Correct	90 ms	6740 KB	Output is correct
10	Correct	2 ms	2644 KB	Output is correct
11	Correct	2 ms	2684 KB	Output is correct
12	Correct	8 ms	2712 KB	Output is correct
13	Correct	7 ms	2644 KB	Output is correct
14	Correct	7 ms	2688 KB	Output is correct
15	Correct	10 ms	3456 KB	Output is correct
16	Correct	18 ms	4272 KB	Output is correct
17	Correct	21 ms	5380 KB	Output is correct
18	Correct	78 ms	6656 KB	Output is correct
19	Incorrect	20 ms	5360 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	26 ms	5564 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Incorrect	20 ms	5584 KB	Output isn't correct
3	Halted	0 ms	0 KB	-