oj.uz

Submission #869687

# Submission time Handle Problem Language Result Execution time Memory
869687 2023-11-05T10:18:57 Z Ahmed_Solyman Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 128340 KB 
/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_cxx;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-O1")
//-------------------------------------------------------------//
typedef long long ll;
typedef unsigned long long ull;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI acos(-1)
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sum_to(n) (n*(n+1))/2
#define pb push_back
#define pf push_front
#define fil(arr,x) memset(arr,x,sizeof(arr))
const ll mod=1e9+7;
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
//-------------------------------------------------------------//
ll lcm(ll a,ll b)
{
    return (max(a,b)/__gcd(a,b))*min(a,b);
}
void person_bool(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
const int N=5005;
int dist[N][N];
vector<int>adj[N];
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #ifndef ONLINE_JUDGE
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    #endif
    fast
    int n,m;cin>>n>>m;
    vector<int>l(n+5),r(n+5);
    for(int i=1;i<=n;i++){
    	cin>>l[i]>>r[i];
    }
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
    		if(i==j)continue;
    		dist[i][j]=1e9;
    		if(r[i]>=l[j] && r[i]<=r[j]){
    			adj[i].push_back(j);
    		}
    	}
    }
    queue<int>q;
    for(int i=1;i<=n;i++){
    	q.push(i);
    	while(q.size()){
    		int x=q.front();
    		q.pop();
    		for(auto j:adj[x]){
    			if(dist[i][j]>dist[i][x]+1){
    				dist[i][j]=dist[i][x]+1;
    				q.push(j);
    			}
    		}
    	}
    }
    while(m--){
    	int a,b;cin>>a>>b;
    	if(dist[a][b]==1e9)cout<<"impossible"<<endl;
    	else cout<<dist[a][b]<<endl;
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Execution timed out 1586 ms 73360 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 12 ms 21180 KB Output is correct
4 Correct 10 ms 21084 KB Output is correct
5 Correct 14 ms 21068 KB Output is correct
6 Correct 57 ms 21956 KB Output is correct
7 Correct 177 ms 22748 KB Output is correct
8 Correct 210 ms 23812 KB Output is correct
9 Correct 1126 ms 25152 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 12 ms 21180 KB Output is correct
4 Correct 10 ms 21084 KB Output is correct
5 Correct 14 ms 21068 KB Output is correct
6 Correct 57 ms 21956 KB Output is correct
7 Correct 177 ms 22748 KB Output is correct
8 Correct 210 ms 23812 KB Output is correct
9 Correct 1126 ms 25152 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 13 ms 21068 KB Output is correct
13 Correct 9 ms 21080 KB Output is correct
14 Correct 14 ms 21080 KB Output is correct
15 Correct 57 ms 21852 KB Output is correct
16 Correct 173 ms 22620 KB Output is correct
17 Correct 206 ms 23812 KB Output is correct
18 Correct 1135 ms 25168 KB Output is correct
19 Execution timed out 1571 ms 128340 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 12 ms 21180 KB Output is correct
4 Correct 10 ms 21084 KB Output is correct
5 Correct 14 ms 21068 KB Output is correct
6 Correct 57 ms 21956 KB Output is correct
7 Correct 177 ms 22748 KB Output is correct
8 Correct 210 ms 23812 KB Output is correct
9 Correct 1126 ms 25152 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 13 ms 21184 KB Output is correct
13 Correct 10 ms 21084 KB Output is correct
14 Correct 14 ms 21088 KB Output is correct
15 Correct 58 ms 21940 KB Output is correct
16 Correct 169 ms 22756 KB Output is correct
17 Correct 218 ms 23892 KB Output is correct
18 Correct 1119 ms 25148 KB Output is correct
19 Execution timed out 1565 ms 77552 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 1531 ms 75740 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 2396 KB Output is correct
2 Execution timed out 1586 ms 73360 KB Time limit exceeded
3 Halted 0 ms 0 KB -