oj.uz

Submission #1119693

# Submission time Handle Problem Language Result Execution time Memory
1119693 2024-11-27T10:04:25 Z thelegendary08 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 250752 KB 
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define vout(v) cout<<#v<<' '; for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	in2(n,q);
	vpii v;
	f0r(i,n){
		in2(a,b);
		v.pb({a,b});
	}
	vvi adj(n);
	f0r(i,n){
		f0r(j,n){
			if(i != j){
				if(v[j].first <= v[i].second && v[i].second <= v[j].second){
					adj[i].pb(j);
				}
			}
		}
	}
	f0r(i,n){
		//vout(adj[i]);
	}
	vvi dist(n,vi(n, 4e18));
	f0r(i,n){
		dist[i][i] = 0;
		priority_queue<pii>pq;
		pq.push({0,i});
		while(!pq.empty()){
			int node = pq.top().second;
			pq.pop();
			for(auto u : adj[node]){
				if(dist[i][u] > dist[i][node] + 1){
					dist[i][u] = dist[i][node] + 1;
					pq.push({-dist[i][u], u});
				}
			}
		}
	}
	f0r(i,n){
		f0r(j,n){
			//cout<<dist[i][j]<<' ';
		}
		//cout<<'\n';
	}
	while(q--){
		in2(a,b);
		a--;
		b--;
		if(dist[a][b] == 4e18)out("impossible");
		else out(dist[a][b]);
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 26 ms 8276 KB Output is correct
4 Correct 24 ms 8428 KB Output is correct
5 Correct 22 ms 8280 KB Output is correct
6 Correct 78 ms 10000 KB Output is correct
7 Correct 181 ms 11604 KB Output is correct
8 Correct 199 ms 13616 KB Output is correct
9 Correct 950 ms 16448 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 26 ms 8276 KB Output is correct
4 Correct 24 ms 8428 KB Output is correct
5 Correct 22 ms 8280 KB Output is correct
6 Correct 78 ms 10000 KB Output is correct
7 Correct 181 ms 11604 KB Output is correct
8 Correct 199 ms 13616 KB Output is correct
9 Correct 950 ms 16448 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 24 ms 8428 KB Output is correct
13 Correct 17 ms 8260 KB Output is correct
14 Correct 25 ms 8276 KB Output is correct
15 Correct 80 ms 9996 KB Output is correct
16 Correct 172 ms 11604 KB Output is correct
17 Correct 190 ms 13748 KB Output is correct
18 Correct 939 ms 16212 KB Output is correct
19 Execution timed out 1572 ms 250752 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 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 26 ms 8276 KB Output is correct
4 Correct 24 ms 8428 KB Output is correct
5 Correct 22 ms 8280 KB Output is correct
6 Correct 78 ms 10000 KB Output is correct
7 Correct 181 ms 11604 KB Output is correct
8 Correct 199 ms 13616 KB Output is correct
9 Correct 950 ms 16448 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 27 ms 8428 KB Output is correct
13 Correct 25 ms 8276 KB Output is correct
14 Correct 31 ms 8276 KB Output is correct
15 Correct 73 ms 9812 KB Output is correct
16 Correct 189 ms 11516 KB Output is correct
17 Correct 191 ms 13628 KB Output is correct
18 Correct 1077 ms 16468 KB Output is correct
19 Execution timed out 1562 ms 6396 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 1555 ms 6532 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 336 KB Output is correct
2 Execution timed out 1589 ms 6404 KB Time limit exceeded
3 Halted 0 ms 0 KB -