oj.uz

Submission #1119717

# Submission time Handle Problem Language Result Execution time Memory
1119717 2024-11-27T10:24:52 Z thelegendary08 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 250700 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;
		queue<int>pq;
		pq.push(i);
		while(!pq.empty()){
			int node = pq.front();
			pq.pop();
			for(auto u : adj[node]){
				if(dist[i][u] == 4e18){
					dist[i][u] = dist[i][node] + 1;
					pq.push(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 1587 ms 6644 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 592 KB Output is correct
3 Correct 16 ms 8272 KB Output is correct
4 Correct 13 ms 8272 KB Output is correct
5 Correct 17 ms 8272 KB Output is correct
6 Correct 71 ms 9872 KB Output is correct
7 Correct 164 ms 11600 KB Output is correct
8 Correct 214 ms 13532 KB Output is correct
9 Correct 996 ms 16416 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 592 KB Output is correct
3 Correct 16 ms 8272 KB Output is correct
4 Correct 13 ms 8272 KB Output is correct
5 Correct 17 ms 8272 KB Output is correct
6 Correct 71 ms 9872 KB Output is correct
7 Correct 164 ms 11600 KB Output is correct
8 Correct 214 ms 13532 KB Output is correct
9 Correct 996 ms 16416 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 18 ms 8272 KB Output is correct
13 Correct 14 ms 8200 KB Output is correct
14 Correct 17 ms 8272 KB Output is correct
15 Correct 57 ms 9808 KB Output is correct
16 Correct 161 ms 11600 KB Output is correct
17 Correct 214 ms 13648 KB Output is correct
18 Correct 1002 ms 16208 KB Output is correct
19 Execution timed out 1568 ms 250700 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 592 KB Output is correct
3 Correct 16 ms 8272 KB Output is correct
4 Correct 13 ms 8272 KB Output is correct
5 Correct 17 ms 8272 KB Output is correct
6 Correct 71 ms 9872 KB Output is correct
7 Correct 164 ms 11600 KB Output is correct
8 Correct 214 ms 13532 KB Output is correct
9 Correct 996 ms 16416 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 15 ms 8272 KB Output is correct
13 Correct 14 ms 8272 KB Output is correct
14 Correct 16 ms 8356 KB Output is correct
15 Correct 73 ms 9808 KB Output is correct
16 Correct 153 ms 11600 KB Output is correct
17 Correct 191 ms 13648 KB Output is correct
18 Correct 1084 ms 16428 KB Output is correct
19 Execution timed out 1553 ms 6440 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 1539 ms 6600 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 1587 ms 6644 KB Time limit exceeded
3 Halted 0 ms 0 KB -