oj.uz

Submission #1119695

# Submission time Handle Problem Language Result Execution time Memory
1119695 2024-11-27T10:05:36 Z thelegendary08 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 250764 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] > dist[i][node] + 1){
					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 1580 ms 6288 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 16 ms 8440 KB Output is correct
4 Correct 12 ms 8272 KB Output is correct
5 Correct 19 ms 8184 KB Output is correct
6 Correct 67 ms 9808 KB Output is correct
7 Correct 212 ms 11600 KB Output is correct
8 Correct 191 ms 13648 KB Output is correct
9 Correct 916 ms 16208 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 16 ms 8440 KB Output is correct
4 Correct 12 ms 8272 KB Output is correct
5 Correct 19 ms 8184 KB Output is correct
6 Correct 67 ms 9808 KB Output is correct
7 Correct 212 ms 11600 KB Output is correct
8 Correct 191 ms 13648 KB Output is correct
9 Correct 916 ms 16208 KB Output is correct
10 Correct 1 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 17 ms 8272 KB Output is correct
15 Correct 67 ms 10060 KB Output is correct
16 Correct 145 ms 11600 KB Output is correct
17 Correct 197 ms 13648 KB Output is correct
18 Correct 950 ms 16208 KB Output is correct
19 Execution timed out 1567 ms 250764 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 16 ms 8440 KB Output is correct
4 Correct 12 ms 8272 KB Output is correct
5 Correct 19 ms 8184 KB Output is correct
6 Correct 67 ms 9808 KB Output is correct
7 Correct 212 ms 11600 KB Output is correct
8 Correct 191 ms 13648 KB Output is correct
9 Correct 916 ms 16208 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 14 ms 8288 KB Output is correct
13 Correct 13 ms 8288 KB Output is correct
14 Correct 16 ms 8292 KB Output is correct
15 Correct 54 ms 9916 KB Output is correct
16 Correct 155 ms 11636 KB Output is correct
17 Correct 180 ms 13696 KB Output is correct
18 Correct 855 ms 16420 KB Output is correct
19 Execution timed out 1554 ms 4760 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 1537 ms 5576 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 1580 ms 6288 KB Time limit exceeded
3 Halted 0 ms 0 KB -