oj.uz

답안 #714300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714300 2023-03-24T08:13:34 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 199636 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

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 98388 KB Output is correct
2 Runtime error 116 ms 199500 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 98400 KB Output is correct
2 Correct 38 ms 98424 KB Output is correct
3 Correct 48 ms 98468 KB Output is correct
4 Correct 51 ms 98508 KB Output is correct
5 Correct 58 ms 98504 KB Output is correct
6 Correct 82 ms 99200 KB Output is correct
7 Correct 166 ms 100064 KB Output is correct
8 Correct 203 ms 101160 KB Output is correct
9 Correct 947 ms 102604 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 98400 KB Output is correct
2 Correct 38 ms 98424 KB Output is correct
3 Correct 48 ms 98468 KB Output is correct
4 Correct 51 ms 98508 KB Output is correct
5 Correct 58 ms 98504 KB Output is correct
6 Correct 82 ms 99200 KB Output is correct
7 Correct 166 ms 100064 KB Output is correct
8 Correct 203 ms 101160 KB Output is correct
9 Correct 947 ms 102604 KB Output is correct
10 Correct 37 ms 98384 KB Output is correct
11 Correct 36 ms 98344 KB Output is correct
12 Correct 53 ms 98412 KB Output is correct
13 Correct 46 ms 98396 KB Output is correct
14 Correct 51 ms 98492 KB Output is correct
15 Correct 82 ms 99296 KB Output is correct
16 Correct 175 ms 100100 KB Output is correct
17 Correct 218 ms 101160 KB Output is correct
18 Correct 1045 ms 102500 KB Output is correct
19 Execution timed out 1579 ms 128404 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 98400 KB Output is correct
2 Correct 38 ms 98424 KB Output is correct
3 Correct 48 ms 98468 KB Output is correct
4 Correct 51 ms 98508 KB Output is correct
5 Correct 58 ms 98504 KB Output is correct
6 Correct 82 ms 99200 KB Output is correct
7 Correct 166 ms 100064 KB Output is correct
8 Correct 203 ms 101160 KB Output is correct
9 Correct 947 ms 102604 KB Output is correct
10 Correct 38 ms 98388 KB Output is correct
11 Correct 37 ms 98448 KB Output is correct
12 Correct 57 ms 98488 KB Output is correct
13 Correct 49 ms 98504 KB Output is correct
14 Correct 52 ms 98508 KB Output is correct
15 Correct 79 ms 99276 KB Output is correct
16 Correct 174 ms 100036 KB Output is correct
17 Correct 214 ms 101080 KB Output is correct
18 Correct 930 ms 102500 KB Output is correct
19 Runtime error 119 ms 199432 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 121 ms 199636 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 98388 KB Output is correct
2 Runtime error 116 ms 199500 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -