oj.uz

Submission #589093

# Submission time Handle Problem Language Result Execution time Memory
589093 2022-07-04T09:17:39 Z sare Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 1512 KB 
//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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Execution timed out 1581 ms 1388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 377 ms 724 KB Output is correct
4 Correct 93 ms 724 KB Output is correct
5 Correct 192 ms 724 KB Output is correct
6 Correct 140 ms 724 KB Output is correct
7 Correct 226 ms 724 KB Output is correct
8 Correct 202 ms 724 KB Output is correct
9 Correct 289 ms 724 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 377 ms 724 KB Output is correct
4 Correct 93 ms 724 KB Output is correct
5 Correct 192 ms 724 KB Output is correct
6 Correct 140 ms 724 KB Output is correct
7 Correct 226 ms 724 KB Output is correct
8 Correct 202 ms 724 KB Output is correct
9 Correct 289 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 382 ms 724 KB Output is correct
13 Correct 91 ms 724 KB Output is correct
14 Correct 179 ms 724 KB Output is correct
15 Correct 128 ms 724 KB Output is correct
16 Correct 229 ms 768 KB Output is correct
17 Correct 204 ms 728 KB Output is correct
18 Correct 292 ms 724 KB Output is correct
19 Execution timed out 1579 ms 752 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 377 ms 724 KB Output is correct
4 Correct 93 ms 724 KB Output is correct
5 Correct 192 ms 724 KB Output is correct
6 Correct 140 ms 724 KB Output is correct
7 Correct 226 ms 724 KB Output is correct
8 Correct 202 ms 724 KB Output is correct
9 Correct 289 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 377 ms 724 KB Output is correct
13 Correct 97 ms 724 KB Output is correct
14 Correct 196 ms 724 KB Output is correct
15 Correct 132 ms 724 KB Output is correct
16 Correct 234 ms 724 KB Output is correct
17 Correct 195 ms 724 KB Output is correct
18 Correct 287 ms 724 KB Output is correct
19 Execution timed out 1547 ms 1512 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 1590 ms 1492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Execution timed out 1581 ms 1388 KB Time limit exceeded
3 Halted 0 ms 0 KB -