oj.uz

답안 #826527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
826527 2023-08-15T16:23:32 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 175 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
#define double long double
const int MAXN = 10400000;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
vector<int>adj[MAXN];
void solve(int tc) {
  int n, m;
  cin >> n >> m;
  int s = sqrt(n);
  int nxt = (s+1) * n;
  for(int i=1; i<=s; i++) {
    for(int j=i*n; j<(i+1)*n; j++) {
      if(j+i < (i+1)*n) adj[j].push_back((j+i) * 2 + 1);
      if(j-i >= i*n) adj[j].push_back((j-i) * 2 + 1);
      adj[j].push_back((j%n) * 2 + 0);
    }
  }
  int st, en;
  for(int i=0; i<m; i++) {
    int b, p;
    cin >> b >> p;
    if(i == 0) st = b;
    if(i == 1) en = b;
    if(p <= s) adj[b].push_back((b+p*n) * 2 + 0);
    else {
      for(int j=b%p; j<n; j+=p) {
        if(j+p < n) adj[nxt + j/p].push_back((nxt + j/p + 1) * 2 + 1);
        if(j-p >= 0) adj[nxt + j/p].push_back((nxt + j/p - 1) * 2 + 1);
        adj[nxt + j/p].push_back(j * 2 + 0);
      }
      adj[b].push_back((nxt + b/p) * 2 + 0);
      for(int j=b%p; j<n; j+=p) {
        nxt++;
      }
    }
  }
  int k = nxt;
  int dist[k];
  //bool vis[k];
  bitset<MAXN>vis;
  for(int i=0; i<k; i++) dist[i] = 1e9, vis[i] = 0;
  dist[st] = 0;
  deque<int> dq;
  dq.push_back(st);
  while(dq.size()) {
    int f = dq.front();
    dq.pop_front();
    if(!vis[f]) {
      vis[f] = 1;
      for(int x: adj[f]) {
        if(!vis[x / 2] && dist[x / 2] > dist[f] + (x % 2)) {
          dist[x / 2] = dist[f] + (x % 2);
          if(x % 2 == 0) dq.push_front(x / 2);
          else dq.push_back(x / 2);
        }
      }
    }
  }
  cout<<(dist[en]==1e9?-1:dist[en])<<"\n";
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷

Compilation message

skyscraper.cpp: In function 'void solve(int)':
skyscraper.cpp:77:17: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |   cout<<(dist[en]==1e9?-1:dist[en])<<"\n";
      |          ~~~~~~~^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 245848 KB Output is correct
2 Correct 169 ms 245788 KB Output is correct
3 Correct 125 ms 245788 KB Output is correct
4 Correct 123 ms 245680 KB Output is correct
5 Correct 110 ms 245816 KB Output is correct
6 Correct 118 ms 245800 KB Output is correct
7 Correct 111 ms 245720 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 245792 KB Output is correct
2 Correct 117 ms 245712 KB Output is correct
3 Correct 109 ms 245768 KB Output is correct
4 Correct 102 ms 245788 KB Output is correct
5 Correct 102 ms 245788 KB Output is correct
6 Correct 111 ms 245796 KB Output is correct
7 Correct 114 ms 245792 KB Output is correct
8 Correct 128 ms 245800 KB Output is correct
9 Correct 139 ms 245756 KB Output is correct
10 Correct 111 ms 245840 KB Output is correct
11 Correct 144 ms 246016 KB Output is correct
12 Correct 117 ms 245760 KB Output is correct
13 Correct 118 ms 245804 KB Output is correct
14 Correct 112 ms 246016 KB Output is correct
15 Correct 118 ms 245964 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 245760 KB Output is correct
2 Correct 101 ms 245704 KB Output is correct
3 Correct 117 ms 245680 KB Output is correct
4 Correct 106 ms 245680 KB Output is correct
5 Correct 103 ms 245700 KB Output is correct
6 Correct 115 ms 245688 KB Output is correct
7 Correct 103 ms 245732 KB Output is correct
8 Correct 109 ms 245768 KB Output is correct
9 Correct 131 ms 245720 KB Output is correct
10 Correct 116 ms 245868 KB Output is correct
11 Correct 103 ms 246020 KB Output is correct
12 Correct 100 ms 245848 KB Output is correct
13 Correct 98 ms 245852 KB Output is correct
14 Correct 110 ms 245944 KB Output is correct
15 Correct 102 ms 245916 KB Output is correct
16 Correct 104 ms 245984 KB Output is correct
17 Correct 109 ms 246748 KB Output is correct
18 Correct 116 ms 248484 KB Output is correct
19 Correct 113 ms 248972 KB Output is correct
20 Correct 117 ms 248908 KB Output is correct
21 Correct 101 ms 246132 KB Output is correct
22 Correct 116 ms 248428 KB Output is correct
23 Correct 116 ms 248112 KB Output is correct
24 Correct 113 ms 248864 KB Output is correct
25 Correct 153 ms 249084 KB Output is correct
26 Correct 126 ms 249036 KB Output is correct
27 Correct 117 ms 248868 KB Output is correct
28 Correct 129 ms 249296 KB Output is correct
29 Correct 132 ms 248832 KB Output is correct
30 Correct 111 ms 248908 KB Output is correct
31 Correct 112 ms 248872 KB Output is correct
32 Correct 145 ms 249320 KB Output is correct
33 Correct 128 ms 250296 KB Output is correct
34 Correct 121 ms 250216 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 245700 KB Output is correct
2 Correct 109 ms 245844 KB Output is correct
3 Correct 132 ms 245704 KB Output is correct
4 Correct 102 ms 245788 KB Output is correct
5 Correct 126 ms 245696 KB Output is correct
6 Correct 119 ms 245784 KB Output is correct
7 Correct 103 ms 245792 KB Output is correct
8 Correct 103 ms 245828 KB Output is correct
9 Correct 102 ms 245812 KB Output is correct
10 Correct 102 ms 245776 KB Output is correct
11 Correct 104 ms 245984 KB Output is correct
12 Correct 101 ms 245740 KB Output is correct
13 Correct 100 ms 245732 KB Output is correct
14 Correct 103 ms 245968 KB Output is correct
15 Correct 106 ms 246092 KB Output is correct
16 Correct 121 ms 245988 KB Output is correct
17 Correct 142 ms 246732 KB Output is correct
18 Correct 108 ms 248360 KB Output is correct
19 Correct 118 ms 248896 KB Output is correct
20 Correct 148 ms 248948 KB Output is correct
21 Correct 105 ms 246100 KB Output is correct
22 Correct 117 ms 248544 KB Output is correct
23 Correct 107 ms 248040 KB Output is correct
24 Correct 114 ms 248864 KB Output is correct
25 Correct 109 ms 249072 KB Output is correct
26 Correct 124 ms 248912 KB Output is correct
27 Correct 112 ms 248928 KB Output is correct
28 Correct 132 ms 249408 KB Output is correct
29 Correct 113 ms 248804 KB Output is correct
30 Correct 108 ms 248896 KB Output is correct
31 Correct 120 ms 248984 KB Output is correct
32 Correct 125 ms 249296 KB Output is correct
33 Correct 122 ms 250260 KB Output is correct
34 Correct 129 ms 250244 KB Output is correct
35 Correct 121 ms 250496 KB Output is correct
36 Correct 134 ms 247520 KB Output is correct
37 Correct 157 ms 253392 KB Output is correct
38 Correct 168 ms 253240 KB Output is correct
39 Correct 175 ms 253320 KB Output is correct
40 Correct 149 ms 253324 KB Output is correct
41 Correct 153 ms 253380 KB Output is correct
42 Correct 123 ms 249244 KB Output is correct
43 Correct 131 ms 249196 KB Output is correct
44 Correct 126 ms 249148 KB Output is correct
45 Runtime error 123 ms 262144 KB Execution killed with signal 9
46 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 245796 KB Output is correct
2 Correct 108 ms 245740 KB Output is correct
3 Correct 120 ms 245760 KB Output is correct
4 Correct 122 ms 245792 KB Output is correct
5 Correct 111 ms 245708 KB Output is correct
6 Correct 101 ms 245800 KB Output is correct
7 Correct 101 ms 245788 KB Output is correct
8 Correct 101 ms 245704 KB Output is correct
9 Correct 110 ms 245740 KB Output is correct
10 Correct 115 ms 245836 KB Output is correct
11 Correct 116 ms 245964 KB Output is correct
12 Correct 110 ms 245968 KB Output is correct
13 Correct 116 ms 245832 KB Output is correct
14 Correct 102 ms 246040 KB Output is correct
15 Correct 110 ms 245944 KB Output is correct
16 Correct 105 ms 245896 KB Output is correct
17 Correct 111 ms 246732 KB Output is correct
18 Correct 107 ms 248444 KB Output is correct
19 Correct 117 ms 248880 KB Output is correct
20 Correct 128 ms 248912 KB Output is correct
21 Correct 145 ms 246032 KB Output is correct
22 Correct 141 ms 248564 KB Output is correct
23 Correct 106 ms 248012 KB Output is correct
24 Correct 133 ms 248884 KB Output is correct
25 Correct 112 ms 249080 KB Output is correct
26 Correct 124 ms 248980 KB Output is correct
27 Correct 127 ms 248968 KB Output is correct
28 Correct 116 ms 249292 KB Output is correct
29 Correct 114 ms 248912 KB Output is correct
30 Correct 111 ms 248904 KB Output is correct
31 Correct 111 ms 248948 KB Output is correct
32 Correct 126 ms 249208 KB Output is correct
33 Correct 124 ms 250244 KB Output is correct
34 Correct 129 ms 250272 KB Output is correct
35 Correct 137 ms 250496 KB Output is correct
36 Correct 126 ms 247456 KB Output is correct
37 Correct 136 ms 253472 KB Output is correct
38 Correct 158 ms 253332 KB Output is correct
39 Correct 151 ms 253340 KB Output is correct
40 Correct 142 ms 253324 KB Output is correct
41 Correct 148 ms 253396 KB Output is correct
42 Correct 115 ms 249272 KB Output is correct
43 Correct 129 ms 249192 KB Output is correct
44 Correct 115 ms 249148 KB Output is correct
45 Runtime error 120 ms 262144 KB Execution killed with signal 9
46 Halted 0 ms 0 KB -