oj.uz

Submission #826531

# Submission time Handle Problem Language Result Execution time Memory
826531 2023-08-15T16:28:04 Z cig32 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 180 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
#define double long double
const int MAXN = 9500000;
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];
  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:76:17: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |   cout<<(dist[en]==1e9?-1:dist[en])<<"\n";
      |          ~~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 223456 KB Output is correct
2 Correct 98 ms 223384 KB Output is correct
3 Correct 99 ms 223380 KB Output is correct
4 Correct 98 ms 223304 KB Output is correct
5 Correct 99 ms 223312 KB Output is correct
6 Correct 98 ms 223332 KB Output is correct
7 Correct 102 ms 223308 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 223396 KB Output is correct
2 Correct 99 ms 223384 KB Output is correct
3 Correct 98 ms 223312 KB Output is correct
4 Correct 98 ms 223364 KB Output is correct
5 Correct 98 ms 223332 KB Output is correct
6 Correct 105 ms 223380 KB Output is correct
7 Correct 98 ms 223392 KB Output is correct
8 Correct 99 ms 223388 KB Output is correct
9 Correct 98 ms 223328 KB Output is correct
10 Correct 101 ms 223464 KB Output is correct
11 Correct 100 ms 223512 KB Output is correct
12 Correct 99 ms 223336 KB Output is correct
13 Correct 100 ms 223400 KB Output is correct
14 Correct 105 ms 223652 KB Output is correct
15 Correct 105 ms 223564 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 223392 KB Output is correct
2 Correct 100 ms 223280 KB Output is correct
3 Correct 100 ms 223388 KB Output is correct
4 Correct 102 ms 223276 KB Output is correct
5 Correct 101 ms 223316 KB Output is correct
6 Correct 101 ms 223292 KB Output is correct
7 Correct 101 ms 223392 KB Output is correct
8 Correct 100 ms 223324 KB Output is correct
9 Correct 110 ms 223436 KB Output is correct
10 Correct 99 ms 223472 KB Output is correct
11 Correct 100 ms 223540 KB Output is correct
12 Correct 99 ms 223448 KB Output is correct
13 Correct 99 ms 223564 KB Output is correct
14 Correct 99 ms 223608 KB Output is correct
15 Correct 109 ms 223568 KB Output is correct
16 Correct 101 ms 223472 KB Output is correct
17 Correct 102 ms 224444 KB Output is correct
18 Correct 105 ms 226052 KB Output is correct
19 Correct 108 ms 226680 KB Output is correct
20 Correct 113 ms 226668 KB Output is correct
21 Correct 108 ms 223700 KB Output is correct
22 Correct 106 ms 226144 KB Output is correct
23 Correct 104 ms 225748 KB Output is correct
24 Correct 107 ms 226636 KB Output is correct
25 Correct 116 ms 226768 KB Output is correct
26 Correct 114 ms 226660 KB Output is correct
27 Correct 109 ms 226636 KB Output is correct
28 Correct 108 ms 226952 KB Output is correct
29 Correct 107 ms 226508 KB Output is correct
30 Correct 110 ms 226672 KB Output is correct
31 Correct 109 ms 226656 KB Output is correct
32 Correct 123 ms 227004 KB Output is correct
33 Correct 112 ms 228000 KB Output is correct
34 Correct 111 ms 228012 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 223356 KB Output is correct
2 Correct 99 ms 223352 KB Output is correct
3 Correct 99 ms 223348 KB Output is correct
4 Correct 108 ms 223392 KB Output is correct
5 Correct 99 ms 223344 KB Output is correct
6 Correct 104 ms 223360 KB Output is correct
7 Correct 99 ms 223308 KB Output is correct
8 Correct 99 ms 223304 KB Output is correct
9 Correct 98 ms 223412 KB Output is correct
10 Correct 99 ms 223468 KB Output is correct
11 Correct 103 ms 223652 KB Output is correct
12 Correct 101 ms 223368 KB Output is correct
13 Correct 99 ms 223420 KB Output is correct
14 Correct 100 ms 223540 KB Output is correct
15 Correct 100 ms 223568 KB Output is correct
16 Correct 101 ms 223520 KB Output is correct
17 Correct 104 ms 224436 KB Output is correct
18 Correct 107 ms 226064 KB Output is correct
19 Correct 112 ms 226680 KB Output is correct
20 Correct 109 ms 226612 KB Output is correct
21 Correct 100 ms 223656 KB Output is correct
22 Correct 107 ms 226116 KB Output is correct
23 Correct 107 ms 225748 KB Output is correct
24 Correct 108 ms 226612 KB Output is correct
25 Correct 125 ms 226696 KB Output is correct
26 Correct 114 ms 226692 KB Output is correct
27 Correct 118 ms 226656 KB Output is correct
28 Correct 110 ms 226888 KB Output is correct
29 Correct 110 ms 226568 KB Output is correct
30 Correct 107 ms 226684 KB Output is correct
31 Correct 120 ms 226628 KB Output is correct
32 Correct 108 ms 227020 KB Output is correct
33 Correct 112 ms 227996 KB Output is correct
34 Correct 118 ms 228016 KB Output is correct
35 Correct 116 ms 228172 KB Output is correct
36 Correct 111 ms 225056 KB Output is correct
37 Correct 126 ms 231228 KB Output is correct
38 Correct 127 ms 231104 KB Output is correct
39 Correct 128 ms 231060 KB Output is correct
40 Correct 126 ms 231116 KB Output is correct
41 Correct 127 ms 231112 KB Output is correct
42 Correct 110 ms 226904 KB Output is correct
43 Correct 110 ms 226868 KB Output is correct
44 Correct 119 ms 226732 KB Output is correct
45 Correct 170 ms 241416 KB Output is correct
46 Correct 168 ms 241404 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 223312 KB Output is correct
2 Correct 100 ms 223388 KB Output is correct
3 Correct 108 ms 223356 KB Output is correct
4 Correct 99 ms 223276 KB Output is correct
5 Correct 100 ms 223356 KB Output is correct
6 Correct 99 ms 223396 KB Output is correct
7 Correct 105 ms 223392 KB Output is correct
8 Correct 102 ms 223376 KB Output is correct
9 Correct 99 ms 223348 KB Output is correct
10 Correct 99 ms 223436 KB Output is correct
11 Correct 111 ms 223528 KB Output is correct
12 Correct 99 ms 223336 KB Output is correct
13 Correct 102 ms 223388 KB Output is correct
14 Correct 101 ms 223704 KB Output is correct
15 Correct 100 ms 223564 KB Output is correct
16 Correct 100 ms 223564 KB Output is correct
17 Correct 104 ms 224332 KB Output is correct
18 Correct 111 ms 226156 KB Output is correct
19 Correct 108 ms 226592 KB Output is correct
20 Correct 108 ms 226648 KB Output is correct
21 Correct 100 ms 223660 KB Output is correct
22 Correct 106 ms 226168 KB Output is correct
23 Correct 106 ms 225724 KB Output is correct
24 Correct 108 ms 226608 KB Output is correct
25 Correct 108 ms 226764 KB Output is correct
26 Correct 107 ms 226636 KB Output is correct
27 Correct 108 ms 226624 KB Output is correct
28 Correct 109 ms 226916 KB Output is correct
29 Correct 109 ms 226572 KB Output is correct
30 Correct 108 ms 226508 KB Output is correct
31 Correct 108 ms 226644 KB Output is correct
32 Correct 111 ms 226928 KB Output is correct
33 Correct 113 ms 228004 KB Output is correct
34 Correct 114 ms 228016 KB Output is correct
35 Correct 117 ms 228228 KB Output is correct
36 Correct 106 ms 225100 KB Output is correct
37 Correct 127 ms 231244 KB Output is correct
38 Correct 130 ms 231072 KB Output is correct
39 Correct 126 ms 231116 KB Output is correct
40 Correct 129 ms 231136 KB Output is correct
41 Correct 128 ms 231196 KB Output is correct
42 Correct 110 ms 226944 KB Output is correct
43 Correct 111 ms 226880 KB Output is correct
44 Correct 109 ms 226812 KB Output is correct
45 Correct 168 ms 241336 KB Output is correct
46 Correct 168 ms 241304 KB Output is correct
47 Runtime error 180 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -