oj.uz

Submission #703955

# Submission time Handle Problem Language Result Execution time Memory
703955 2023-03-01T06:02:42 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 40600 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 6 ms 804 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 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 18 ms 8404 KB Output is correct
4 Correct 12 ms 8404 KB Output is correct
5 Correct 17 ms 8384 KB Output is correct
6 Correct 49 ms 9092 KB Output is correct
7 Correct 134 ms 9940 KB Output is correct
8 Correct 162 ms 11056 KB Output is correct
9 Correct 859 ms 12364 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 18 ms 8404 KB Output is correct
4 Correct 12 ms 8404 KB Output is correct
5 Correct 17 ms 8384 KB Output is correct
6 Correct 49 ms 9092 KB Output is correct
7 Correct 134 ms 9940 KB Output is correct
8 Correct 162 ms 11056 KB Output is correct
9 Correct 859 ms 12364 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 16 ms 8424 KB Output is correct
13 Correct 13 ms 8404 KB Output is correct
14 Correct 18 ms 8316 KB Output is correct
15 Correct 50 ms 9164 KB Output is correct
16 Correct 135 ms 9892 KB Output is correct
17 Correct 157 ms 10956 KB Output is correct
18 Correct 818 ms 12388 KB Output is correct
19 Execution timed out 1577 ms 40600 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 18 ms 8404 KB Output is correct
4 Correct 12 ms 8404 KB Output is correct
5 Correct 17 ms 8384 KB Output is correct
6 Correct 49 ms 9092 KB Output is correct
7 Correct 134 ms 9940 KB Output is correct
8 Correct 162 ms 11056 KB Output is correct
9 Correct 859 ms 12364 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 16 ms 8416 KB Output is correct
13 Correct 12 ms 8412 KB Output is correct
14 Correct 17 ms 8404 KB Output is correct
15 Correct 49 ms 9180 KB Output is correct
16 Correct 133 ms 9936 KB Output is correct
17 Correct 160 ms 10972 KB Output is correct
18 Correct 845 ms 12408 KB Output is correct
19 Runtime error 3 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 804 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 6 ms 804 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -