Submission #589093

#	Time	Username	Problem	Language	Result	Execution time	Memory
589093		sare	Event Hopping (BOI22_events)	C++17	10 / 100	1590 ms	1512 KiB

events

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e5 + 10;
int s[MAXN], e[MAXN], n, m, dis[MAXN];

int main() {
	ios::sync_with_stdio(0);
#ifndef LOCAL
	cin.tie(0);
#endif
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s[i] >> e[i];
	}
	while (m--) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		queue<int> q;
		memset(dis, 63, sizeof(dis));
		q.push(u);
		dis[u] = 0;
		while (q.size()) {
			int f = q.front();
			q.pop();
			for (int i = 0; i < n; i++) {
				if (s[i] <= e[f] && e[f] <= e[i] && dis[i] > dis[f] + 1) {
					dis[i] = dis[f] + 1;
					q.push(i);
				}
			}
		}
		if (dis[v] == dis[n]) {
			cout << "impossible" << '\n';
		}
		else {
			cout << dis[v] << '\n';
		}
	}
}

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