oj.uz

Submission #714307

# Submission time Handle Problem Language Result Execution time Memory
714307 2023-03-24T08:24:36 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 199552 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[a]-nm[b]<<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 36 ms 98412 KB Output is correct
2 Runtime error 119 ms 199552 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 36 ms 98476 KB Output is correct
2 Correct 36 ms 98372 KB Output is correct
3 Correct 50 ms 98604 KB Output is correct
4 Correct 45 ms 98508 KB Output is correct
5 Correct 54 ms 98484 KB Output is correct
6 Correct 106 ms 99304 KB Output is correct
7 Correct 162 ms 100080 KB Output is correct
8 Correct 192 ms 101092 KB Output is correct
9 Correct 877 ms 102516 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 98476 KB Output is correct
2 Correct 36 ms 98372 KB Output is correct
3 Correct 50 ms 98604 KB Output is correct
4 Correct 45 ms 98508 KB Output is correct
5 Correct 54 ms 98484 KB Output is correct
6 Correct 106 ms 99304 KB Output is correct
7 Correct 162 ms 100080 KB Output is correct
8 Correct 192 ms 101092 KB Output is correct
9 Correct 877 ms 102516 KB Output is correct
10 Correct 42 ms 98460 KB Output is correct
11 Correct 36 ms 98480 KB Output is correct
12 Correct 50 ms 98472 KB Output is correct
13 Correct 45 ms 98508 KB Output is correct
14 Correct 50 ms 98448 KB Output is correct
15 Correct 100 ms 99308 KB Output is correct
16 Correct 177 ms 100108 KB Output is correct
17 Correct 188 ms 101164 KB Output is correct
18 Correct 902 ms 102516 KB Output is correct
19 Execution timed out 1580 ms 128456 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 98476 KB Output is correct
2 Correct 36 ms 98372 KB Output is correct
3 Correct 50 ms 98604 KB Output is correct
4 Correct 45 ms 98508 KB Output is correct
5 Correct 54 ms 98484 KB Output is correct
6 Correct 106 ms 99304 KB Output is correct
7 Correct 162 ms 100080 KB Output is correct
8 Correct 192 ms 101092 KB Output is correct
9 Correct 877 ms 102516 KB Output is correct
10 Correct 41 ms 98472 KB Output is correct
11 Correct 38 ms 98380 KB Output is correct
12 Correct 50 ms 98432 KB Output is correct
13 Correct 45 ms 98508 KB Output is correct
14 Correct 54 ms 98440 KB Output is correct
15 Correct 89 ms 99292 KB Output is correct
16 Correct 175 ms 100204 KB Output is correct
17 Correct 189 ms 101204 KB Output is correct
18 Correct 910 ms 102516 KB Output is correct
19 Runtime error 122 ms 199500 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 143 ms 199504 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 36 ms 98412 KB Output is correct
2 Runtime error 119 ms 199552 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -