oj.uz

답안 #549050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
549050 2022-04-15T03:35:46 Z czhang2718 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 139 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;

typedef pair<int,int> pii;
#define f first
#define s second
#define nl '\n'
#define pb push_back
#define sz(x) (int) x.size()

const int N=30001;
const int B=175;
const int MX=10000000;
int n,m;
vector<int> v[N];
int P[N], x[N];
int dist[N][B];
bool done[N][B];
vector<pii> todo[MX];

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for(int i=0; i<m; i++){
    cin >> x[i] >> P[i];
    v[x[i]].push_back(i);
  }
  for(int i=0; i<n; i++){
    for(int j=0; j<B; j++) dist[i][j]=1e9;
  }
  dist[x[0]][0]=0;

  set<pair<int, pii>> s;

  auto go=[&](int i, int d, int b){
    for(int c:{i+b, i-b}){
      if(c<0 || c>=n) continue;
      if(d+1<dist[c][b]){
        dist[c][b]=d+1;
        todo[d+1].pb({c, b});
      }
      if(d+1<dist[c][0]){
        dist[c][0]=d+1;
        todo[d+1].pb({c, 0});
      }
    }
  };

  todo[0].pb({x[0], 0});
  int d=0;
  while(true){
    pii p;
    while(true){
      while(d<MX && !sz(todo[d])) d++;
      if(d==MX) break;
      p=todo[d].back();
      todo[d].pop_back();
      if(!done[p.f][p.s]) break;
    }
    if(d==MX) break;
    int a=p.f, b=p.s;
    done[a][b]=1;
    // cout << a << " " << b << nl;
    if(a==x[1]){
      cout << d; return 0;
    }
    if(!b){
      for(int i:v[a]){
        if(P[i]>=B){
          for(int j=a%P[i]; j<n; j+=P[i]){
            if(d+abs(j-a)/P[i]<dist[j][0]){
              dist[j][0]=d+abs(j-a)/P[i];
              todo[dist[j][0]].pb({j, 0});
            }
          }
        }
        else{
          go(a, d, P[i]);
        }
      }
    }
    else{
      go(a, d, b);
    }
  }
  cout << -1;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 235888 KB Output is correct
2 Correct 106 ms 235840 KB Output is correct
3 Correct 105 ms 235828 KB Output is correct
4 Correct 126 ms 235876 KB Output is correct
5 Correct 105 ms 235884 KB Output is correct
6 Correct 107 ms 235768 KB Output is correct
7 Correct 108 ms 235852 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 235812 KB Output is correct
2 Correct 107 ms 235756 KB Output is correct
3 Correct 113 ms 235832 KB Output is correct
4 Correct 122 ms 235796 KB Output is correct
5 Correct 107 ms 235800 KB Output is correct
6 Correct 105 ms 235756 KB Output is correct
7 Correct 104 ms 235768 KB Output is correct
8 Correct 122 ms 235900 KB Output is correct
9 Correct 108 ms 235844 KB Output is correct
10 Correct 108 ms 236024 KB Output is correct
11 Correct 110 ms 235984 KB Output is correct
12 Correct 108 ms 235980 KB Output is correct
13 Correct 110 ms 235932 KB Output is correct
14 Correct 107 ms 235924 KB Output is correct
15 Correct 107 ms 235940 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 235812 KB Output is correct
2 Correct 105 ms 235980 KB Output is correct
3 Correct 112 ms 235840 KB Output is correct
4 Correct 121 ms 235872 KB Output is correct
5 Correct 108 ms 235832 KB Output is correct
6 Correct 108 ms 235852 KB Output is correct
7 Correct 109 ms 235836 KB Output is correct
8 Correct 106 ms 235844 KB Output is correct
9 Correct 106 ms 235860 KB Output is correct
10 Correct 108 ms 235952 KB Output is correct
11 Correct 111 ms 235924 KB Output is correct
12 Correct 107 ms 235920 KB Output is correct
13 Correct 109 ms 235964 KB Output is correct
14 Correct 108 ms 235980 KB Output is correct
15 Correct 108 ms 235964 KB Output is correct
16 Correct 125 ms 235996 KB Output is correct
17 Correct 109 ms 236568 KB Output is correct
18 Correct 123 ms 237172 KB Output is correct
19 Correct 125 ms 237240 KB Output is correct
20 Correct 108 ms 237600 KB Output is correct
21 Correct 123 ms 236292 KB Output is correct
22 Correct 122 ms 237120 KB Output is correct
23 Correct 108 ms 237236 KB Output is correct
24 Correct 111 ms 237532 KB Output is correct
25 Correct 110 ms 237628 KB Output is correct
26 Correct 110 ms 237580 KB Output is correct
27 Correct 112 ms 237712 KB Output is correct
28 Correct 110 ms 238140 KB Output is correct
29 Correct 110 ms 238284 KB Output is correct
30 Correct 111 ms 237764 KB Output is correct
31 Correct 112 ms 238012 KB Output is correct
32 Correct 113 ms 237808 KB Output is correct
33 Correct 110 ms 238796 KB Output is correct
34 Correct 110 ms 238232 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 235868 KB Output is correct
2 Correct 116 ms 235860 KB Output is correct
3 Correct 112 ms 235916 KB Output is correct
4 Correct 124 ms 235872 KB Output is correct
5 Correct 117 ms 235764 KB Output is correct
6 Correct 107 ms 235792 KB Output is correct
7 Correct 106 ms 235756 KB Output is correct
8 Correct 106 ms 235852 KB Output is correct
9 Correct 108 ms 235968 KB Output is correct
10 Correct 107 ms 235852 KB Output is correct
11 Correct 107 ms 235920 KB Output is correct
12 Correct 106 ms 235956 KB Output is correct
13 Correct 107 ms 235880 KB Output is correct
14 Correct 109 ms 236108 KB Output is correct
15 Correct 107 ms 235976 KB Output is correct
16 Correct 122 ms 235912 KB Output is correct
17 Correct 106 ms 236492 KB Output is correct
18 Correct 126 ms 236980 KB Output is correct
19 Correct 124 ms 237400 KB Output is correct
20 Correct 115 ms 237636 KB Output is correct
21 Correct 122 ms 236108 KB Output is correct
22 Correct 123 ms 237056 KB Output is correct
23 Correct 112 ms 237316 KB Output is correct
24 Correct 108 ms 237540 KB Output is correct
25 Correct 108 ms 237528 KB Output is correct
26 Correct 108 ms 237624 KB Output is correct
27 Correct 107 ms 237700 KB Output is correct
28 Correct 110 ms 238108 KB Output is correct
29 Correct 108 ms 238272 KB Output is correct
30 Correct 107 ms 237712 KB Output is correct
31 Correct 112 ms 238028 KB Output is correct
32 Correct 126 ms 237820 KB Output is correct
33 Correct 117 ms 238876 KB Output is correct
34 Correct 108 ms 238156 KB Output is correct
35 Correct 111 ms 237628 KB Output is correct
36 Correct 108 ms 236772 KB Output is correct
37 Correct 128 ms 237924 KB Output is correct
38 Correct 114 ms 238096 KB Output is correct
39 Correct 111 ms 237704 KB Output is correct
40 Correct 113 ms 237824 KB Output is correct
41 Correct 110 ms 238120 KB Output is correct
42 Correct 112 ms 238056 KB Output is correct
43 Correct 113 ms 237988 KB Output is correct
44 Correct 112 ms 238052 KB Output is correct
45 Correct 130 ms 240884 KB Output is correct
46 Correct 116 ms 239540 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 235780 KB Output is correct
2 Correct 110 ms 235936 KB Output is correct
3 Correct 109 ms 235852 KB Output is correct
4 Correct 123 ms 235868 KB Output is correct
5 Correct 107 ms 235868 KB Output is correct
6 Correct 108 ms 235760 KB Output is correct
7 Correct 105 ms 235800 KB Output is correct
8 Correct 106 ms 235784 KB Output is correct
9 Correct 105 ms 235852 KB Output is correct
10 Correct 109 ms 235964 KB Output is correct
11 Correct 107 ms 235972 KB Output is correct
12 Correct 107 ms 235892 KB Output is correct
13 Correct 107 ms 235976 KB Output is correct
14 Correct 109 ms 235976 KB Output is correct
15 Correct 106 ms 235904 KB Output is correct
16 Correct 123 ms 235988 KB Output is correct
17 Correct 108 ms 236536 KB Output is correct
18 Correct 132 ms 237000 KB Output is correct
19 Correct 139 ms 237256 KB Output is correct
20 Correct 110 ms 237644 KB Output is correct
21 Correct 131 ms 236096 KB Output is correct
22 Correct 126 ms 237112 KB Output is correct
23 Correct 111 ms 237304 KB Output is correct
24 Correct 108 ms 237560 KB Output is correct
25 Correct 109 ms 237516 KB Output is correct
26 Correct 108 ms 237572 KB Output is correct
27 Correct 109 ms 237644 KB Output is correct
28 Correct 111 ms 238060 KB Output is correct
29 Correct 110 ms 238284 KB Output is correct
30 Correct 108 ms 237708 KB Output is correct
31 Correct 109 ms 238032 KB Output is correct
32 Correct 111 ms 237880 KB Output is correct
33 Correct 111 ms 238776 KB Output is correct
34 Correct 109 ms 238192 KB Output is correct
35 Correct 113 ms 237532 KB Output is correct
36 Correct 114 ms 236864 KB Output is correct
37 Correct 111 ms 237896 KB Output is correct
38 Correct 114 ms 238056 KB Output is correct
39 Correct 126 ms 237652 KB Output is correct
40 Correct 113 ms 237864 KB Output is correct
41 Correct 113 ms 238116 KB Output is correct
42 Correct 112 ms 237976 KB Output is correct
43 Correct 115 ms 237984 KB Output is correct
44 Correct 112 ms 237940 KB Output is correct
45 Correct 121 ms 240936 KB Output is correct
46 Correct 116 ms 239372 KB Output is correct
47 Correct 126 ms 247192 KB Output is correct
48 Correct 136 ms 252412 KB Output is correct
49 Correct 138 ms 253896 KB Output is correct
50 Correct 134 ms 255384 KB Output is correct
51 Runtime error 112 ms 262144 KB Execution killed with signal 9
52 Halted 0 ms 0 KB -