oj.uz

Submission #699969

# Submission time Handle Problem Language Result Execution time Memory
699969 2023-02-18T12:13:57 Z Abrar_Al_Samit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 145 ms 63832 KB 
#include<bits/stdc++.h>
using namespace std;
 
const int nax = 3e4 + 3;
const int INF = 1e9;
const long long pr = 1e9 + 9;
const int cax = 1e6 + 3;
 
int b[nax], p[nax];
vector<int>doges[nax];
 
vector<pair<long long,int>>dist[cax];
int get(int x, int y) {
  long long H = x * pr + y;
  int H2 = H % cax;
  for(auto x : dist[H2]) {
    if(x.first==H) return x.second;
  }
  return INF;
}
void put(int x, int y, int val) {
  long long H = x * pr + y;
  int H2 = H % cax;
  dist[H2].emplace_back(H, val);
  assert(dist[H2].size()<=5);
}
void PlayGround() {
  int n, m;
  cin>>n>>m;
 
  for(int i=0; i<m; ++i) {
    cin>>b[i]>>p[i];
    doges[b[i]].push_back(p[i]);
  }
 
  put(b[0], 0, 0);
 
  deque<tuple<int,int,int>>dq;
  dq.push_back({b[0], 0, 0});
 
  while(!dq.empty()) {
    auto x = dq.front();
    dq.pop_front();
    int ss, j, d;
    tie(ss, j, d) = x;
    if(d!=get(ss, j)) continue;
    if(ss==b[1]) {
      cout<<d<<'\n';
      return;
    }
 
 
    if(j==0) {
      for(int z : doges[ss]) {
        if(get(ss, z)>d) {
          put(ss, z, d);
          dq.emplace_front(ss, z, d);
        }
      }
    } else {
      if(ss+j<n) {
        if(get(ss+j, j)>d+1) {
          put(ss+j, j, d+1);
          dq.emplace_back(ss+j, j, d+1);
        }
        if(get(ss+j, 0)>d+1) {
          put(ss+j, 0, d+1);
          dq.emplace_back(ss+j, 0, d+1);
        }
      }
      if(ss-j>=0) {
        if(get(ss-j, j)>d+1) {
          put(ss-j, j, d+1);
          dq.emplace_back(ss-j, j, d+1);
        }
        if(get(ss-j, 0)>d+1) {
          put(ss-j, 0, d+1);
          dq.emplace_back(ss-j, 0, d+1);
        }
      }
    }
  }
  cout<<"-1\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24404 KB Output is correct
2 Correct 13 ms 24460 KB Output is correct
3 Correct 13 ms 24404 KB Output is correct
4 Correct 13 ms 24456 KB Output is correct
5 Correct 13 ms 24404 KB Output is correct
6 Correct 13 ms 24412 KB Output is correct
7 Correct 12 ms 24404 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24488 KB Output is correct
2 Correct 13 ms 24488 KB Output is correct
3 Correct 12 ms 24404 KB Output is correct
4 Correct 12 ms 24424 KB Output is correct
5 Correct 14 ms 24532 KB Output is correct
6 Correct 12 ms 24504 KB Output is correct
7 Correct 13 ms 24404 KB Output is correct
8 Correct 13 ms 24404 KB Output is correct
9 Correct 14 ms 24404 KB Output is correct
10 Correct 13 ms 24508 KB Output is correct
11 Correct 13 ms 24472 KB Output is correct
12 Correct 13 ms 24536 KB Output is correct
13 Correct 12 ms 24532 KB Output is correct
14 Correct 13 ms 24660 KB Output is correct
15 Correct 13 ms 24660 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24428 KB Output is correct
2 Correct 12 ms 24404 KB Output is correct
3 Correct 14 ms 24404 KB Output is correct
4 Correct 12 ms 24404 KB Output is correct
5 Correct 13 ms 24404 KB Output is correct
6 Correct 15 ms 24400 KB Output is correct
7 Correct 13 ms 24404 KB Output is correct
8 Correct 12 ms 24512 KB Output is correct
9 Correct 13 ms 24424 KB Output is correct
10 Correct 13 ms 24532 KB Output is correct
11 Correct 16 ms 24472 KB Output is correct
12 Correct 16 ms 24532 KB Output is correct
13 Correct 13 ms 24508 KB Output is correct
14 Correct 15 ms 24692 KB Output is correct
15 Correct 13 ms 24656 KB Output is correct
16 Correct 13 ms 24532 KB Output is correct
17 Correct 14 ms 24636 KB Output is correct
18 Correct 13 ms 24532 KB Output is correct
19 Correct 13 ms 24532 KB Output is correct
20 Correct 14 ms 24660 KB Output is correct
21 Correct 13 ms 24532 KB Output is correct
22 Correct 13 ms 24436 KB Output is correct
23 Correct 16 ms 24676 KB Output is correct
24 Correct 15 ms 24788 KB Output is correct
25 Correct 14 ms 24604 KB Output is correct
26 Correct 14 ms 24692 KB Output is correct
27 Correct 15 ms 24672 KB Output is correct
28 Correct 17 ms 25272 KB Output is correct
29 Correct 21 ms 26412 KB Output is correct
30 Correct 16 ms 25044 KB Output is correct
31 Correct 17 ms 25524 KB Output is correct
32 Correct 16 ms 25332 KB Output is correct
33 Correct 31 ms 28152 KB Output is correct
34 Correct 22 ms 26644 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24448 KB Output is correct
2 Correct 12 ms 24488 KB Output is correct
3 Correct 12 ms 24404 KB Output is correct
4 Correct 12 ms 24404 KB Output is correct
5 Correct 12 ms 24508 KB Output is correct
6 Correct 13 ms 24404 KB Output is correct
7 Correct 12 ms 24500 KB Output is correct
8 Correct 13 ms 24456 KB Output is correct
9 Correct 13 ms 24436 KB Output is correct
10 Correct 13 ms 24420 KB Output is correct
11 Correct 13 ms 24532 KB Output is correct
12 Correct 12 ms 24532 KB Output is correct
13 Correct 14 ms 24532 KB Output is correct
14 Correct 14 ms 24740 KB Output is correct
15 Correct 14 ms 24696 KB Output is correct
16 Correct 14 ms 24532 KB Output is correct
17 Correct 14 ms 24660 KB Output is correct
18 Correct 13 ms 24532 KB Output is correct
19 Correct 15 ms 24532 KB Output is correct
20 Correct 13 ms 24660 KB Output is correct
21 Correct 13 ms 24500 KB Output is correct
22 Correct 13 ms 24516 KB Output is correct
23 Correct 14 ms 24660 KB Output is correct
24 Correct 14 ms 24808 KB Output is correct
25 Correct 14 ms 24524 KB Output is correct
26 Correct 16 ms 24660 KB Output is correct
27 Correct 14 ms 24720 KB Output is correct
28 Correct 17 ms 25184 KB Output is correct
29 Correct 22 ms 26452 KB Output is correct
30 Correct 15 ms 25056 KB Output is correct
31 Correct 17 ms 25604 KB Output is correct
32 Correct 16 ms 25300 KB Output is correct
33 Correct 33 ms 28156 KB Output is correct
34 Correct 25 ms 26584 KB Output is correct
35 Correct 26 ms 26472 KB Output is correct
36 Correct 14 ms 24660 KB Output is correct
37 Correct 21 ms 26068 KB Output is correct
38 Correct 22 ms 25684 KB Output is correct
39 Correct 18 ms 24892 KB Output is correct
40 Correct 19 ms 25164 KB Output is correct
41 Correct 27 ms 26788 KB Output is correct
42 Correct 16 ms 24916 KB Output is correct
43 Correct 19 ms 24968 KB Output is correct
44 Correct 18 ms 25008 KB Output is correct
45 Correct 140 ms 38264 KB Output is correct
46 Correct 83 ms 33008 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24404 KB Output is correct
2 Correct 13 ms 24404 KB Output is correct
3 Correct 13 ms 24404 KB Output is correct
4 Correct 13 ms 24516 KB Output is correct
5 Correct 13 ms 24420 KB Output is correct
6 Correct 16 ms 24492 KB Output is correct
7 Correct 12 ms 24404 KB Output is correct
8 Correct 14 ms 24536 KB Output is correct
9 Correct 13 ms 24504 KB Output is correct
10 Correct 13 ms 24548 KB Output is correct
11 Correct 15 ms 24532 KB Output is correct
12 Correct 13 ms 24552 KB Output is correct
13 Correct 13 ms 24532 KB Output is correct
14 Correct 13 ms 24624 KB Output is correct
15 Correct 14 ms 24660 KB Output is correct
16 Correct 13 ms 24532 KB Output is correct
17 Correct 13 ms 24672 KB Output is correct
18 Correct 15 ms 24508 KB Output is correct
19 Correct 13 ms 24532 KB Output is correct
20 Correct 14 ms 24660 KB Output is correct
21 Correct 13 ms 24532 KB Output is correct
22 Correct 13 ms 24484 KB Output is correct
23 Correct 16 ms 24660 KB Output is correct
24 Correct 15 ms 24768 KB Output is correct
25 Correct 14 ms 24512 KB Output is correct
26 Correct 14 ms 24660 KB Output is correct
27 Correct 14 ms 24660 KB Output is correct
28 Correct 17 ms 25172 KB Output is correct
29 Correct 23 ms 26496 KB Output is correct
30 Correct 17 ms 25100 KB Output is correct
31 Correct 17 ms 25568 KB Output is correct
32 Correct 16 ms 25328 KB Output is correct
33 Correct 33 ms 28088 KB Output is correct
34 Correct 22 ms 26524 KB Output is correct
35 Correct 26 ms 26580 KB Output is correct
36 Correct 14 ms 24660 KB Output is correct
37 Correct 22 ms 26144 KB Output is correct
38 Correct 22 ms 25684 KB Output is correct
39 Correct 20 ms 24916 KB Output is correct
40 Correct 21 ms 25224 KB Output is correct
41 Correct 27 ms 26800 KB Output is correct
42 Correct 18 ms 24916 KB Output is correct
43 Correct 17 ms 25008 KB Output is correct
44 Correct 17 ms 25044 KB Output is correct
45 Correct 145 ms 38304 KB Output is correct
46 Correct 85 ms 33020 KB Output is correct
47 Correct 26 ms 26592 KB Output is correct
48 Correct 19 ms 25120 KB Output is correct
49 Correct 18 ms 25064 KB Output is correct
50 Correct 19 ms 24988 KB Output is correct
51 Correct 36 ms 27656 KB Output is correct
52 Correct 37 ms 27964 KB Output is correct
53 Correct 22 ms 25584 KB Output is correct
54 Correct 16 ms 25428 KB Output is correct
55 Correct 19 ms 25900 KB Output is correct
56 Correct 27 ms 27436 KB Output is correct
57 Correct 14 ms 24532 KB Output is correct
58 Correct 33 ms 27788 KB Output is correct
59 Correct 34 ms 27512 KB Output is correct
60 Correct 34 ms 27472 KB Output is correct
61 Correct 31 ms 27312 KB Output is correct
62 Runtime error 96 ms 63832 KB Execution killed with signal 6
63 Halted 0 ms 0 KB -