Submission #703951

#	Time	Username	Problem	Language	Result	Execution time	Memory
703951		vjudge1	Event Hopping (BOI22_events)	C++17	10 / 100	1591 ms	32876 KiB

events

#include <bits/stdc++.h>                     
  
#define ll long long 
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) (int)v.size()
#define x first
#define y second
#define nl "\n"
  
using namespace std;
  
const int N = (int)1e5 + 7;
const int M = (int)2e6 + 5e5 + 7;
const ll MOD = (ll)1e9;                    
const int inf = (int)1e9 + 7;
const int B = (int)390;
const ll INF = (ll)1e18 + 7;
  
pair<int, int> dir[] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
 
bool bit(int mask, int i) {
    return (mask >> i & 1);
}
  
int sum(int x, int y) {
    x += y;
    if(x >= MOD) x -= MOD;
    return x;
}
  
int mult(int x, int y) {
    return 1ll * x * y % MOD;
}

int n, q;
int l[N], r[N], d[N];
vector<int> g[N];

void solve() {	
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		cin >> l[i] >> r[i];
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			if(l[j] <= r[i] && r[i] <= r[j]) {
				g[i].pb(j);
			}
		}
	}

	while(q--) {
		int s, t;
		cin >> s >> t;
		queue<int> q;
		fill(d + 1, d + 1 + n, inf);
		d[s] = 0;
		q.push(s);
		while(!q.empty()) {
			int v = q.front();
			q.pop();
			for(auto to : g[v]) {
				if(d[v] + 1 < d[to]) {
					d[to] = d[v] + 1;
					q.push(to);
				}
			}
		}
		if(d[t] == inf) cout << "impossible\n";
		else cout << d[t] << nl;			
	}
}       
 
  
signed main() {                   
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int test = 1;                       
    //cin >> test;
    for(int i = 1; i <= test; ++i) {
        //cout << "Case " << i << ":\n";
        solve();
    }
    return 0;
}                   
/*
possible causes of error :
* array  bounds
* int overflow
* special case (n == 1?)
* haven't clean something
* wrong N | M | inf | INF | MOD

* try to write brute force to find test
* don't waste time
* don't write bullshit
* solution is easy
*/

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