oj.uz

Submission #714319

# Submission time Handle Problem Language Result Execution time Memory
714319 2023-03-24T08:37:35 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 199548 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],p[mxn*100],nm[mxn*100];
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 solve2(){
    vector<pair<pii,int>>vt;
    for(int i=1;i<=n;i++){
        vt.pb({{x[i],y[i]},i});
    }
    sort(all(vt));
    for(int i=1;i<vt.size();i++){
        if(vt[i].F.F<=vt[i-1].F.S&&vt[i-1].F.S<=vt[i].F.S){
            p[i]=p[i-1];
        }
        else{
            p[i]=p[i-1]+1;
        }
    }
    for(int i=0;i<vt.size();i++){
        nm[vt[i].S]=i;
    }
    while(m--){
        int a,b;
        cin>>a>>b;
        if(nm[a]<nm[b]&&p[nm[b]]-p[nm[a]]==0){
            cout<<nm[b]-nm[a]<<endl;
        }
        else{
            cout<<"impossible"<<endl;
        }
    }
}
void solve(){
    memset(dis,-1,sizeof(dis));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    if(n>5000){
        solve2();
        return;
    }
    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;
}

Compilation message

events.cpp: In function 'void solve2()':
events.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=1;i<vt.size();i++){
      |                 ~^~~~~~~~~~
events.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<vt.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 98380 KB Output is correct
2 Runtime error 122 ms 199456 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 39 ms 98356 KB Output is correct
2 Correct 46 ms 98396 KB Output is correct
3 Correct 54 ms 98604 KB Output is correct
4 Correct 45 ms 98416 KB Output is correct
5 Correct 56 ms 98468 KB Output is correct
6 Correct 90 ms 99308 KB Output is correct
7 Correct 175 ms 100124 KB Output is correct
8 Correct 224 ms 101156 KB Output is correct
9 Correct 911 ms 102604 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 98356 KB Output is correct
2 Correct 46 ms 98396 KB Output is correct
3 Correct 54 ms 98604 KB Output is correct
4 Correct 45 ms 98416 KB Output is correct
5 Correct 56 ms 98468 KB Output is correct
6 Correct 90 ms 99308 KB Output is correct
7 Correct 175 ms 100124 KB Output is correct
8 Correct 224 ms 101156 KB Output is correct
9 Correct 911 ms 102604 KB Output is correct
10 Correct 47 ms 98384 KB Output is correct
11 Correct 45 ms 98380 KB Output is correct
12 Correct 59 ms 98488 KB Output is correct
13 Correct 56 ms 98420 KB Output is correct
14 Correct 64 ms 98524 KB Output is correct
15 Correct 92 ms 99276 KB Output is correct
16 Correct 163 ms 100108 KB Output is correct
17 Correct 189 ms 101196 KB Output is correct
18 Correct 882 ms 102512 KB Output is correct
19 Execution timed out 1577 ms 128448 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 98356 KB Output is correct
2 Correct 46 ms 98396 KB Output is correct
3 Correct 54 ms 98604 KB Output is correct
4 Correct 45 ms 98416 KB Output is correct
5 Correct 56 ms 98468 KB Output is correct
6 Correct 90 ms 99308 KB Output is correct
7 Correct 175 ms 100124 KB Output is correct
8 Correct 224 ms 101156 KB Output is correct
9 Correct 911 ms 102604 KB Output is correct
10 Correct 47 ms 98380 KB Output is correct
11 Correct 41 ms 98420 KB Output is correct
12 Correct 51 ms 98496 KB Output is correct
13 Correct 47 ms 98436 KB Output is correct
14 Correct 53 ms 98504 KB Output is correct
15 Correct 82 ms 99276 KB Output is correct
16 Correct 175 ms 100048 KB Output is correct
17 Correct 192 ms 101068 KB Output is correct
18 Correct 877 ms 102536 KB Output is correct
19 Runtime error 122 ms 199460 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 118 ms 199548 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 42 ms 98380 KB Output is correct
2 Runtime error 122 ms 199456 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -