제출 #1120159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120159		vjudge1	Event Hopping (BOI22_events)	C++17	10 / 100	1566 ms	200416 KiB

events

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>

#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bitcount(n) __builtin_popcountll(n)
#define all(x) x.begin(), x.end()
#define len(s) (int) s.size()
#define md ((l + r) >> 1)

#define pb push_back
#define S second
#define F first

// #define int long long

using namespace std;

typedef int ll;
typedef long double ld;

const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int N = 5e3 + 11;
const int MAX = (1 << 16);
const int mod = 998244353;
const long long inf = 1e9 + 10;
const double eps = 1e-9;

ll n, q;
ll l[N], r[N], d[N][N];

bool was[N];

vector < ll > g[N];

void bfs(ll s){
	queue < ll > q;
	fill(was, was + N, 0);
	d[s][s] = 0, was[s] = 1;
	q.push(s);
	while(!q.empty()){
		ll v = q.front();
		q.pop();
		for(ll u : g[v])
			if(!was[u])
				d[s][u] = d[s][v] + 1, q.push(u), was[u] = 1;
	}
}

void output(){
	cin >> n >> q;
	for(ll i = 0; i < N; i++)
		for(ll j = 0; j < N; j++)
			d[i][j] = -1;
	for(ll i = 1; i <= n; i++) cin >> l[i] >> r[i];
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= n; j++){
			if(l[j] <= r[i] && r[i] <= r[j]){
				g[i].pb(j);
			}
		}
	}
	for(ll i = 1; i <= n; i++){
		bfs(i);
	}
	while(q--){
		ll s, f;
		cin >> s >> f;
		if(d[s][f] == -1) cout << "impossible\n";
		else cout << d[s][f] << '\n';
	}
}

const bool cases = 0;

signed main(){
//  file("disrupt");
    adiyer();
    int tt = 1;
    if(cases) cin >> tt;
    for(int i = 1; i <= tt; i++){
		output();
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30