oj.uz

답안 #699978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699978 2023-02-18T12:17:46 Z Abrar_Al_Samit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 99744 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()<=10);
}
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});
 
  set<pair<int,int>>s;
  while(!dq.empty()) {
    auto x = dq.front();
    dq.pop_front();
    int ss, j, d;
    tie(ss, j, d) = x;

    if(s.find(make_pair(ss, j))!=s.end()) continue;
    s.insert({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 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 15 ms 24496 KB Output is correct
5 Correct 14 ms 24428 KB Output is correct
6 Correct 13 ms 24448 KB Output is correct
7 Correct 13 ms 24404 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 24404 KB Output is correct
2 Correct 13 ms 24396 KB Output is correct
3 Correct 12 ms 24508 KB Output is correct
4 Correct 14 ms 24436 KB Output is correct
5 Correct 13 ms 24420 KB Output is correct
6 Correct 12 ms 24408 KB Output is correct
7 Correct 12 ms 24404 KB Output is correct
8 Correct 12 ms 24504 KB Output is correct
9 Correct 14 ms 24404 KB Output is correct
10 Correct 15 ms 24532 KB Output is correct
11 Correct 14 ms 24532 KB Output is correct
12 Correct 14 ms 24448 KB Output is correct
13 Correct 13 ms 24564 KB Output is correct
14 Correct 17 ms 25024 KB Output is correct
15 Correct 14 ms 24792 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24404 KB Output is correct
2 Correct 12 ms 24404 KB Output is correct
3 Correct 13 ms 24492 KB Output is correct
4 Correct 12 ms 24416 KB Output is correct
5 Correct 13 ms 24508 KB Output is correct
6 Correct 13 ms 24508 KB Output is correct
7 Correct 13 ms 24404 KB Output is correct
8 Correct 13 ms 24404 KB Output is correct
9 Correct 12 ms 24424 KB Output is correct
10 Correct 13 ms 24444 KB Output is correct
11 Correct 13 ms 24532 KB Output is correct
12 Correct 16 ms 24504 KB Output is correct
13 Correct 13 ms 24464 KB Output is correct
14 Correct 15 ms 24916 KB Output is correct
15 Correct 14 ms 24788 KB Output is correct
16 Correct 13 ms 24536 KB Output is correct
17 Correct 15 ms 24788 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 24788 KB Output is correct
21 Correct 13 ms 24544 KB Output is correct
22 Correct 13 ms 24532 KB Output is correct
23 Correct 19 ms 25008 KB Output is correct
24 Correct 17 ms 25184 KB Output is correct
25 Correct 13 ms 24532 KB Output is correct
26 Correct 16 ms 24792 KB Output is correct
27 Correct 16 ms 24916 KB Output is correct
28 Correct 23 ms 26196 KB Output is correct
29 Correct 48 ms 29312 KB Output is correct
30 Correct 20 ms 25968 KB Output is correct
31 Correct 28 ms 27168 KB Output is correct
32 Correct 24 ms 26452 KB Output is correct
33 Correct 98 ms 34004 KB Output is correct
34 Correct 48 ms 29648 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24404 KB Output is correct
2 Correct 12 ms 24432 KB Output is correct
3 Correct 12 ms 24404 KB Output is correct
4 Correct 13 ms 24496 KB Output is correct
5 Correct 13 ms 24496 KB Output is correct
6 Correct 14 ms 24408 KB Output is correct
7 Correct 13 ms 24404 KB Output is correct
8 Correct 13 ms 24404 KB Output is correct
9 Correct 15 ms 24440 KB Output is correct
10 Correct 15 ms 24532 KB Output is correct
11 Correct 13 ms 24524 KB Output is correct
12 Correct 13 ms 24520 KB Output is correct
13 Correct 13 ms 24552 KB Output is correct
14 Correct 15 ms 24916 KB Output is correct
15 Correct 14 ms 24752 KB Output is correct
16 Correct 13 ms 24532 KB Output is correct
17 Correct 15 ms 24780 KB Output is correct
18 Correct 13 ms 24432 KB Output is correct
19 Correct 13 ms 24532 KB Output is correct
20 Correct 14 ms 24912 KB Output is correct
21 Correct 13 ms 24504 KB Output is correct
22 Correct 14 ms 24476 KB Output is correct
23 Correct 16 ms 24916 KB Output is correct
24 Correct 17 ms 25180 KB Output is correct
25 Correct 14 ms 24660 KB Output is correct
26 Correct 15 ms 24800 KB Output is correct
27 Correct 15 ms 24996 KB Output is correct
28 Correct 23 ms 26184 KB Output is correct
29 Correct 45 ms 29388 KB Output is correct
30 Correct 21 ms 25900 KB Output is correct
31 Correct 32 ms 27220 KB Output is correct
32 Correct 23 ms 26404 KB Output is correct
33 Correct 95 ms 34036 KB Output is correct
34 Correct 49 ms 29668 KB Output is correct
35 Correct 38 ms 28236 KB Output is correct
36 Correct 15 ms 24728 KB Output is correct
37 Correct 25 ms 26828 KB Output is correct
38 Correct 24 ms 26320 KB Output is correct
39 Correct 19 ms 24896 KB Output is correct
40 Correct 20 ms 25300 KB Output is correct
41 Correct 36 ms 28204 KB Output is correct
42 Correct 17 ms 25112 KB Output is correct
43 Correct 20 ms 25300 KB Output is correct
44 Correct 17 ms 25140 KB Output is correct
45 Correct 544 ms 62648 KB Output is correct
46 Correct 208 ms 44392 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24496 KB Output is correct
2 Correct 12 ms 24452 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 12 ms 24404 KB Output is correct
7 Correct 12 ms 24404 KB Output is correct
8 Correct 12 ms 24404 KB Output is correct
9 Correct 13 ms 24496 KB Output is correct
10 Correct 13 ms 24524 KB Output is correct
11 Correct 13 ms 24472 KB Output is correct
12 Correct 12 ms 24532 KB Output is correct
13 Correct 13 ms 24532 KB Output is correct
14 Correct 15 ms 24916 KB Output is correct
15 Correct 13 ms 24788 KB Output is correct
16 Correct 13 ms 24444 KB Output is correct
17 Correct 14 ms 24832 KB Output is correct
18 Correct 12 ms 24532 KB Output is correct
19 Correct 13 ms 24532 KB Output is correct
20 Correct 14 ms 24800 KB Output is correct
21 Correct 13 ms 24532 KB Output is correct
22 Correct 13 ms 24544 KB Output is correct
23 Correct 16 ms 25004 KB Output is correct
24 Correct 16 ms 25124 KB Output is correct
25 Correct 13 ms 24532 KB Output is correct
26 Correct 16 ms 24788 KB Output is correct
27 Correct 15 ms 24944 KB Output is correct
28 Correct 23 ms 26240 KB Output is correct
29 Correct 47 ms 29348 KB Output is correct
30 Correct 19 ms 25940 KB Output is correct
31 Correct 28 ms 27148 KB Output is correct
32 Correct 25 ms 26508 KB Output is correct
33 Correct 103 ms 34024 KB Output is correct
34 Correct 50 ms 29644 KB Output is correct
35 Correct 36 ms 28132 KB Output is correct
36 Correct 16 ms 24736 KB Output is correct
37 Correct 29 ms 26832 KB Output is correct
38 Correct 24 ms 26328 KB Output is correct
39 Correct 20 ms 24916 KB Output is correct
40 Correct 21 ms 25308 KB Output is correct
41 Correct 35 ms 28284 KB Output is correct
42 Correct 17 ms 25216 KB Output is correct
43 Correct 20 ms 25304 KB Output is correct
44 Correct 17 ms 25156 KB Output is correct
45 Correct 515 ms 62640 KB Output is correct
46 Correct 231 ms 44356 KB Output is correct
47 Correct 32 ms 27540 KB Output is correct
48 Correct 19 ms 25132 KB Output is correct
49 Correct 17 ms 25044 KB Output is correct
50 Correct 15 ms 24916 KB Output is correct
51 Correct 59 ms 30672 KB Output is correct
52 Correct 67 ms 31424 KB Output is correct
53 Correct 23 ms 26164 KB Output is correct
54 Correct 23 ms 26804 KB Output is correct
55 Correct 28 ms 27900 KB Output is correct
56 Correct 40 ms 30332 KB Output is correct
57 Correct 13 ms 24636 KB Output is correct
58 Correct 59 ms 32304 KB Output is correct
59 Correct 57 ms 31436 KB Output is correct
60 Correct 56 ms 31436 KB Output is correct
61 Correct 55 ms 30924 KB Output is correct
62 Correct 491 ms 61848 KB Output is correct
63 Execution timed out 1099 ms 99744 KB Time limit exceeded
64 Halted 0 ms 0 KB -