oj.uz

Submission #589020

# Submission time Handle Problem Language Result Execution time Memory
589020 2022-07-04T08:52:26 Z shayanebrahimi Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 60856 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl                        '\n'
#define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll MOD=1e9+7;//998244353//1e9+9//1111211111;
//ll tavmd(ll a,ll b){if(b==0){return 1;}if(b%2==0){ll x=tavmd(a,b/2);return(x*x)%MOD;}else{return(a%MOD*tavmd(a,b-1)%MOD)%MOD;}}
const ll MAXN=2e5+10;
const ll INF=8e18;
const ll LOG=30;
ll s[MAXN],e[MAXN],n,q,d[MAXN];
vector<ll>adj[MAXN];
int main(){
      fast_io;
      fill(d,d+MAXN,INF);
      cin>>n>>q;
      for(int i=1;i<=n;i++){
            cin>>s[i]>>e[i];
      }
      for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                  if(i!=j&&e[i]>=s[j]&&e[i]<=e[j]){
                        adj[i].push_back(j);
                  }
            }
      }
      while(q--){
            fill(d,d+MAXN,INF);
            ll u,v;
            cin>>u>>v;
            d[u]=0;
            queue<ll>pq;
            pq.push(u);
            while(!pq.empty()){
                  ll x=pq.front();
                  pq.pop();
                  for(auto i:adj[x]){
                        if(d[i]==INF){
                              d[i]=d[x]+1;
                              pq.push(i);
                        }
                  }
            }
            if(d[v]==INF)
                  cout<<"impossible"<<endl;
            else
                  cout<<d[v]<<endl;
      }
      return 0;
}

Compilation message

events.cpp:5:9: warning: ISO C++11 requires whitespace after the macro name
    5 | #define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
      |         ^~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6504 KB Output is correct
2 Execution timed out 1563 ms 8236 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 23 ms 6632 KB Output is correct
4 Correct 28 ms 6612 KB Output is correct
5 Correct 23 ms 6640 KB Output is correct
6 Correct 27 ms 8148 KB Output is correct
7 Correct 59 ms 9848 KB Output is correct
8 Correct 45 ms 11860 KB Output is correct
9 Correct 110 ms 14636 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 23 ms 6632 KB Output is correct
4 Correct 28 ms 6612 KB Output is correct
5 Correct 23 ms 6640 KB Output is correct
6 Correct 27 ms 8148 KB Output is correct
7 Correct 59 ms 9848 KB Output is correct
8 Correct 45 ms 11860 KB Output is correct
9 Correct 110 ms 14636 KB Output is correct
10 Correct 6 ms 6592 KB Output is correct
11 Correct 6 ms 6484 KB Output is correct
12 Correct 33 ms 6620 KB Output is correct
13 Correct 22 ms 6640 KB Output is correct
14 Correct 35 ms 6612 KB Output is correct
15 Correct 28 ms 8224 KB Output is correct
16 Correct 37 ms 9848 KB Output is correct
17 Correct 38 ms 11860 KB Output is correct
18 Correct 132 ms 14532 KB Output is correct
19 Execution timed out 1577 ms 60856 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 23 ms 6632 KB Output is correct
4 Correct 28 ms 6612 KB Output is correct
5 Correct 23 ms 6640 KB Output is correct
6 Correct 27 ms 8148 KB Output is correct
7 Correct 59 ms 9848 KB Output is correct
8 Correct 45 ms 11860 KB Output is correct
9 Correct 110 ms 14636 KB Output is correct
10 Correct 6 ms 6612 KB Output is correct
11 Correct 6 ms 6588 KB Output is correct
12 Correct 43 ms 6620 KB Output is correct
13 Correct 22 ms 6648 KB Output is correct
14 Correct 27 ms 6644 KB Output is correct
15 Correct 35 ms 8224 KB Output is correct
16 Correct 49 ms 9848 KB Output is correct
17 Correct 68 ms 11932 KB Output is correct
18 Correct 135 ms 14636 KB Output is correct
19 Execution timed out 1576 ms 8300 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 1567 ms 8372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6504 KB Output is correct
2 Execution timed out 1563 ms 8236 KB Time limit exceeded
3 Halted 0 ms 0 KB -