oj.uz

Submission #714320

# Submission time Handle Problem Language Result Execution time Memory
714320 2023-03-24T08:38:36 Z Khizri Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 199564 KB 
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
//------------------------------DEFINE------------------------------
//******************************************************************
#define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
//******************************************************************
//----------------------------FUNCTION------------------------------
//******************************************************************
ll gcd(ll a,ll b){
    if(a>b) swap(a,b);
    if(a==0) return a+b;
    return gcd(b%a,a);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
bool is_prime(ll n){
    ll k=sqrt(n);

    if(n==2) return true;
    if(n<2||n%2==0||k*k==n) return false;
    for(int i=3;i<=k;i+=2){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
//*****************************************************************
//--------------------------MAIN-CODE------------------------------
const int mxn=5e3+5;
int t=1,n,m,x[mxn],y[mxn],dis[mxn][mxn];
vector<int>vt[mxn];
void bfs(int k){
    queue<int>q;
    q.push(k);
    dis[k][k]=0;
    while(q.size()>0){
        int u=q.front();
        q.pop();
        for(int v:vt[u]){
            if(dis[k][v]==-1){
                dis[k][v]=dis[k][u]+1;
                q.push(v);
            }
        }
    }
}
void solve(){
    memset(dis,-1,sizeof(dis));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(x[j]<=y[i]&&y[i]<=y[j]){
                vt[i].pb(j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        bfs(i);
    }
    while(m--){
        int a,b;
        cin>>a>>b;
        if(dis[a][b]==-1){
            cout<<"impossible"<<endl;
        }
        else{
            cout<<dis[a][b]<<endl;
        }
    }
}
int main(){
    IOS;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98448 KB Output is correct
2 Runtime error 117 ms 199564 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 37 ms 98428 KB Output is correct
2 Correct 37 ms 98380 KB Output is correct
3 Correct 52 ms 98412 KB Output is correct
4 Correct 45 ms 98424 KB Output is correct
5 Correct 52 ms 98456 KB Output is correct
6 Correct 79 ms 99264 KB Output is correct
7 Correct 166 ms 100112 KB Output is correct
8 Correct 190 ms 101108 KB Output is correct
9 Correct 877 ms 102500 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98428 KB Output is correct
2 Correct 37 ms 98380 KB Output is correct
3 Correct 52 ms 98412 KB Output is correct
4 Correct 45 ms 98424 KB Output is correct
5 Correct 52 ms 98456 KB Output is correct
6 Correct 79 ms 99264 KB Output is correct
7 Correct 166 ms 100112 KB Output is correct
8 Correct 190 ms 101108 KB Output is correct
9 Correct 877 ms 102500 KB Output is correct
10 Correct 38 ms 98388 KB Output is correct
11 Correct 37 ms 98416 KB Output is correct
12 Correct 51 ms 98380 KB Output is correct
13 Correct 46 ms 98448 KB Output is correct
14 Correct 53 ms 98508 KB Output is correct
15 Correct 81 ms 99288 KB Output is correct
16 Correct 167 ms 100020 KB Output is correct
17 Correct 200 ms 101196 KB Output is correct
18 Correct 891 ms 102504 KB Output is correct
19 Execution timed out 1583 ms 128412 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98428 KB Output is correct
2 Correct 37 ms 98380 KB Output is correct
3 Correct 52 ms 98412 KB Output is correct
4 Correct 45 ms 98424 KB Output is correct
5 Correct 52 ms 98456 KB Output is correct
6 Correct 79 ms 99264 KB Output is correct
7 Correct 166 ms 100112 KB Output is correct
8 Correct 190 ms 101108 KB Output is correct
9 Correct 877 ms 102500 KB Output is correct
10 Correct 38 ms 98460 KB Output is correct
11 Correct 36 ms 98352 KB Output is correct
12 Correct 51 ms 98504 KB Output is correct
13 Correct 48 ms 98512 KB Output is correct
14 Correct 52 ms 98416 KB Output is correct
15 Correct 83 ms 99296 KB Output is correct
16 Correct 169 ms 100096 KB Output is correct
17 Correct 193 ms 101160 KB Output is correct
18 Correct 868 ms 102536 KB Output is correct
19 Runtime error 119 ms 199484 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 115 ms 199492 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 37 ms 98448 KB Output is correct
2 Runtime error 117 ms 199564 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -