oj.uz

Submission #703961

# Submission time Handle Problem Language Result Execution time Memory
703961 2023-03-01T06:15:36 Z vjlinkhero Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 39824 KB 
/*#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
  
#define fix fixed<<setprecision
#define forn(i, n) for(int i = 1; i <= (n); ++i)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(s) (int) (s).size()
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ss second
#define ff first

using namespace std;
using namespace __gnu_pbds;
using pii = pair<int,int>;
using pll = pair<long long, long long>;
using ll = long long;
using ull = unsigned long long;

 
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 5e3+100, inf = 1e9+7;
int n, q, s[N], e[N], d[N][N];
vector<int> g[N];


int main(){
	//freopen("cownomics.in", "r", stdin);
	//freopen("cownomics.out", "w", stdout);
	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];
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			if(i != j && s[j] <= e[i] && e[i] <= e[j])
				g[i].pb(j);
	for(int v = 1; v <= n; ++v){
		for(int u = 1; u <= n; ++u)
			d[v][u] = inf;
		d[v][v] = 0;
		queue<int> q;
		q.push(v);
		while(!q.empty()){
			int i = q.front();
			q.pop();
			for(auto to : g[i])
				if(d[v][to] == inf){
					d[v][to] = d[v][i] + 1;
					q.push(to);
				}
		}
	}
	while(q--){
		int a, b;
		cin >> a >> b;
		if(d[a][b] == inf)
			cout << "impossible\n";
		else
			cout << d[a][b] << '\n';
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 5 ms 724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 19 ms 8372 KB Output is correct
4 Correct 14 ms 8352 KB Output is correct
5 Correct 22 ms 8404 KB Output is correct
6 Correct 66 ms 9152 KB Output is correct
7 Correct 181 ms 9932 KB Output is correct
8 Correct 211 ms 11008 KB Output is correct
9 Correct 1018 ms 12348 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 19 ms 8372 KB Output is correct
4 Correct 14 ms 8352 KB Output is correct
5 Correct 22 ms 8404 KB Output is correct
6 Correct 66 ms 9152 KB Output is correct
7 Correct 181 ms 9932 KB Output is correct
8 Correct 211 ms 11008 KB Output is correct
9 Correct 1018 ms 12348 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 18 ms 8428 KB Output is correct
13 Correct 16 ms 8368 KB Output is correct
14 Correct 20 ms 8404 KB Output is correct
15 Correct 60 ms 9160 KB Output is correct
16 Correct 153 ms 9952 KB Output is correct
17 Correct 210 ms 11064 KB Output is correct
18 Correct 896 ms 12416 KB Output is correct
19 Execution timed out 1588 ms 39824 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 19 ms 8372 KB Output is correct
4 Correct 14 ms 8352 KB Output is correct
5 Correct 22 ms 8404 KB Output is correct
6 Correct 66 ms 9152 KB Output is correct
7 Correct 181 ms 9932 KB Output is correct
8 Correct 211 ms 11008 KB Output is correct
9 Correct 1018 ms 12348 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 16 ms 8340 KB Output is correct
13 Correct 12 ms 8332 KB Output is correct
14 Correct 17 ms 8420 KB Output is correct
15 Correct 51 ms 9156 KB Output is correct
16 Correct 137 ms 10008 KB Output is correct
17 Correct 161 ms 11084 KB Output is correct
18 Correct 882 ms 12360 KB Output is correct
19 Runtime error 6 ms 724 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 5 ms 724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -