oj.uz

답안 #699983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699983 2023-02-18T12:26:54 Z Abrar_Al_Samit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 137676 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];
vector<long long>done[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()<=10);
}
bool cek(int x, int y) {
  long long H = x * pr + y;
  int H2 = H % cax;

  for(auto x : done[H2]) {
    if(x==H) return true;
  }
  return false;
}
void push(int x, int y) {
  long long H = x * pr + y;
  int H2 = H % cax;
  done[H2].push_back(H);
}
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(cek(ss, j)) continue;
    push(ss, j);

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 47948 KB Output is correct
2 Correct 25 ms 47976 KB Output is correct
3 Correct 27 ms 47948 KB Output is correct
4 Correct 26 ms 47904 KB Output is correct
5 Correct 31 ms 47976 KB Output is correct
6 Correct 23 ms 47928 KB Output is correct
7 Correct 28 ms 47936 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 47956 KB Output is correct
2 Correct 24 ms 47952 KB Output is correct
3 Correct 24 ms 47956 KB Output is correct
4 Correct 24 ms 47956 KB Output is correct
5 Correct 24 ms 47928 KB Output is correct
6 Correct 27 ms 47956 KB Output is correct
7 Correct 28 ms 47956 KB Output is correct
8 Correct 23 ms 47900 KB Output is correct
9 Correct 30 ms 47956 KB Output is correct
10 Correct 25 ms 47968 KB Output is correct
11 Correct 25 ms 48048 KB Output is correct
12 Correct 24 ms 47948 KB Output is correct
13 Correct 23 ms 48028 KB Output is correct
14 Correct 24 ms 48304 KB Output is correct
15 Correct 24 ms 48216 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47884 KB Output is correct
2 Correct 23 ms 47992 KB Output is correct
3 Correct 23 ms 47984 KB Output is correct
4 Correct 25 ms 47972 KB Output is correct
5 Correct 23 ms 47960 KB Output is correct
6 Correct 24 ms 47948 KB Output is correct
7 Correct 29 ms 48068 KB Output is correct
8 Correct 26 ms 47900 KB Output is correct
9 Correct 24 ms 47916 KB Output is correct
10 Correct 27 ms 48028 KB Output is correct
11 Correct 24 ms 48168 KB Output is correct
12 Correct 25 ms 47956 KB Output is correct
13 Correct 25 ms 47968 KB Output is correct
14 Correct 26 ms 48412 KB Output is correct
15 Correct 24 ms 48188 KB Output is correct
16 Correct 24 ms 47984 KB Output is correct
17 Correct 26 ms 48188 KB Output is correct
18 Correct 24 ms 47956 KB Output is correct
19 Correct 26 ms 48028 KB Output is correct
20 Correct 26 ms 48308 KB Output is correct
21 Correct 26 ms 48032 KB Output is correct
22 Correct 23 ms 47956 KB Output is correct
23 Correct 26 ms 48356 KB Output is correct
24 Correct 28 ms 48532 KB Output is correct
25 Correct 26 ms 48028 KB Output is correct
26 Correct 25 ms 48308 KB Output is correct
27 Correct 26 ms 48340 KB Output is correct
28 Correct 33 ms 49424 KB Output is correct
29 Correct 46 ms 51872 KB Output is correct
30 Correct 30 ms 49108 KB Output is correct
31 Correct 37 ms 50100 KB Output is correct
32 Correct 33 ms 49564 KB Output is correct
33 Correct 65 ms 54636 KB Output is correct
34 Correct 44 ms 52068 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 47980 KB Output is correct
2 Correct 25 ms 48000 KB Output is correct
3 Correct 22 ms 47952 KB Output is correct
4 Correct 22 ms 47960 KB Output is correct
5 Correct 25 ms 47952 KB Output is correct
6 Correct 28 ms 47908 KB Output is correct
7 Correct 24 ms 47956 KB Output is correct
8 Correct 24 ms 47956 KB Output is correct
9 Correct 24 ms 47976 KB Output is correct
10 Correct 23 ms 47988 KB Output is correct
11 Correct 24 ms 48044 KB Output is correct
12 Correct 25 ms 47952 KB Output is correct
13 Correct 28 ms 47932 KB Output is correct
14 Correct 24 ms 48396 KB Output is correct
15 Correct 24 ms 48172 KB Output is correct
16 Correct 25 ms 47924 KB Output is correct
17 Correct 25 ms 48164 KB Output is correct
18 Correct 25 ms 48084 KB Output is correct
19 Correct 23 ms 47956 KB Output is correct
20 Correct 25 ms 48212 KB Output is correct
21 Correct 24 ms 47960 KB Output is correct
22 Correct 24 ms 48016 KB Output is correct
23 Correct 26 ms 48340 KB Output is correct
24 Correct 27 ms 48512 KB Output is correct
25 Correct 25 ms 48104 KB Output is correct
26 Correct 24 ms 48276 KB Output is correct
27 Correct 27 ms 48408 KB Output is correct
28 Correct 31 ms 49364 KB Output is correct
29 Correct 54 ms 51752 KB Output is correct
30 Correct 31 ms 49160 KB Output is correct
31 Correct 37 ms 50168 KB Output is correct
32 Correct 36 ms 49488 KB Output is correct
33 Correct 66 ms 54608 KB Output is correct
34 Correct 46 ms 52068 KB Output is correct
35 Correct 45 ms 51148 KB Output is correct
36 Correct 29 ms 48104 KB Output is correct
37 Correct 37 ms 50088 KB Output is correct
38 Correct 36 ms 49636 KB Output is correct
39 Correct 29 ms 48392 KB Output is correct
40 Correct 30 ms 48736 KB Output is correct
41 Correct 44 ms 51276 KB Output is correct
42 Correct 30 ms 48596 KB Output is correct
43 Correct 34 ms 48652 KB Output is correct
44 Correct 28 ms 48632 KB Output is correct
45 Correct 263 ms 70308 KB Output is correct
46 Correct 160 ms 63196 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47948 KB Output is correct
2 Correct 27 ms 47992 KB Output is correct
3 Correct 27 ms 47956 KB Output is correct
4 Correct 24 ms 47904 KB Output is correct
5 Correct 24 ms 47976 KB Output is correct
6 Correct 25 ms 47956 KB Output is correct
7 Correct 25 ms 47928 KB Output is correct
8 Correct 23 ms 47972 KB Output is correct
9 Correct 25 ms 48008 KB Output is correct
10 Correct 24 ms 47968 KB Output is correct
11 Correct 24 ms 47956 KB Output is correct
12 Correct 27 ms 47940 KB Output is correct
13 Correct 23 ms 47956 KB Output is correct
14 Correct 26 ms 48332 KB Output is correct
15 Correct 25 ms 48244 KB Output is correct
16 Correct 23 ms 48008 KB Output is correct
17 Correct 25 ms 48244 KB Output is correct
18 Correct 25 ms 47956 KB Output is correct
19 Correct 24 ms 47904 KB Output is correct
20 Correct 25 ms 48212 KB Output is correct
21 Correct 24 ms 47952 KB Output is correct
22 Correct 26 ms 47948 KB Output is correct
23 Correct 26 ms 48380 KB Output is correct
24 Correct 27 ms 48472 KB Output is correct
25 Correct 25 ms 48024 KB Output is correct
26 Correct 25 ms 48240 KB Output is correct
27 Correct 26 ms 48308 KB Output is correct
28 Correct 36 ms 49328 KB Output is correct
29 Correct 54 ms 51844 KB Output is correct
30 Correct 30 ms 49100 KB Output is correct
31 Correct 34 ms 50108 KB Output is correct
32 Correct 30 ms 49596 KB Output is correct
33 Correct 64 ms 54604 KB Output is correct
34 Correct 44 ms 52044 KB Output is correct
35 Correct 43 ms 51084 KB Output is correct
36 Correct 25 ms 48132 KB Output is correct
37 Correct 37 ms 50064 KB Output is correct
38 Correct 35 ms 49528 KB Output is correct
39 Correct 30 ms 48340 KB Output is correct
40 Correct 34 ms 48752 KB Output is correct
41 Correct 45 ms 51268 KB Output is correct
42 Correct 29 ms 48524 KB Output is correct
43 Correct 30 ms 48724 KB Output is correct
44 Correct 30 ms 48544 KB Output is correct
45 Correct 268 ms 70220 KB Output is correct
46 Correct 157 ms 63120 KB Output is correct
47 Correct 42 ms 50636 KB Output is correct
48 Correct 29 ms 48568 KB Output is correct
49 Correct 29 ms 48504 KB Output is correct
50 Correct 27 ms 48388 KB Output is correct
51 Correct 62 ms 53160 KB Output is correct
52 Correct 68 ms 53696 KB Output is correct
53 Correct 35 ms 49408 KB Output is correct
54 Correct 34 ms 49860 KB Output is correct
55 Correct 45 ms 50756 KB Output is correct
56 Correct 54 ms 52708 KB Output is correct
57 Correct 24 ms 48084 KB Output is correct
58 Correct 63 ms 54244 KB Output is correct
59 Correct 63 ms 53612 KB Output is correct
60 Correct 63 ms 53580 KB Output is correct
61 Correct 59 ms 53208 KB Output is correct
62 Correct 287 ms 75192 KB Output is correct
63 Execution timed out 1093 ms 137676 KB Time limit exceeded
64 Halted 0 ms 0 KB -