oj.uz

Submission #826644

# Submission time Handle Problem Language Result Execution time Memory
826644 2023-08-15T18:52:53 Z cig32 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 463 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
#define double long double
const int MAXN = 15000000;
const int MAXN2 = 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 << ": "; }
int n, m, s, nxt;
pair<int, int> cmds[MAXN];
int adj[MAXN];
int id;
int ps[MAXN2];
int cur[MAXN2];
void add_command(int u, int v) {
  cmds[id] = {u,v};
  ps[u]++;
  id++;
}
void construct(int b, int p) { 
  for(int j=b%p; j<n; j+=p) {
    if(j+p < n) add_command(nxt + j/p, (nxt + j/p + 1) * 2 + 1); //adj[nxt + j/p].push_back((nxt + j/p + 1) * 2 + 1);
    if(j-p >= 0) add_command(nxt + j/p, (nxt + j/p - 1) * 2 + 1); //adj[nxt + j/p].push_back((nxt + j/p - 1) * 2 + 1);
    add_command(nxt + j/p, j * 2); //adj[nxt + j/p].push_back(j * 2 + 0);
  }
  add_command(b, (nxt + b/p) * 2); //adj[b].push_back((nxt + b/p) * 2 + 0);
  for(int j=b%p; j<n; j+=p) {
    nxt++;
  }
}
void solve(int tc) {
  cin >> n >> m;
  s = ceil(sqrt(n));
  nxt = n;
  int st, en;
  int bruh[s+1][s];
  for(int i=1; i<=s; i++) {
    for(int j=0; j<i; j++) {
      bruh[i][j] = -1;
    }
  }
  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 && bruh[p][b%p] == -1) {
      bruh[p][b%p] = nxt;
      construct(b, p);
    }
    else if(p > s) {
      construct(b, p);
    }
    else {
      add_command(b, (bruh[p][b%p] + b/p) * 2);
      //adj[b].push_back((bruh[p][b%p] + b/p) * 2 + 0);
    }
  }
  for(int i=1; i<MAXN2; i++) ps[i]+=ps[i-1];
  for(int i=0; i<MAXN2; i++) cur[i]=ps[i]-1;
  for(int i=0; i<id; i++) {
    int u = cmds[i].first, v = cmds[i].second;
    adj[cur[u]] = v;
    cur[u]--;
  }
  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;
      int l, r;
      if(f==0) l=0, r=ps[0]-1;
      else l=ps[f-1], r=ps[f]-1;
      for(int y=l; y<=r; y++) {
        int x = adj[y];
        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:106:17: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |   cout<<(dist[en]==1e9?-1:dist[en])<<"\n";
      |          ~~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 81620 KB Output is correct
2 Correct 69 ms 81684 KB Output is correct
3 Correct 74 ms 81716 KB Output is correct
4 Correct 60 ms 81692 KB Output is correct
5 Correct 65 ms 81720 KB Output is correct
6 Correct 67 ms 81664 KB Output is correct
7 Correct 59 ms 81604 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 81700 KB Output is correct
2 Correct 61 ms 81700 KB Output is correct
3 Correct 63 ms 81724 KB Output is correct
4 Correct 59 ms 81652 KB Output is correct
5 Correct 57 ms 81712 KB Output is correct
6 Correct 57 ms 81612 KB Output is correct
7 Correct 73 ms 81680 KB Output is correct
8 Correct 61 ms 81704 KB Output is correct
9 Correct 70 ms 81688 KB Output is correct
10 Correct 63 ms 81704 KB Output is correct
11 Correct 69 ms 81868 KB Output is correct
12 Correct 60 ms 81644 KB Output is correct
13 Correct 72 ms 81660 KB Output is correct
14 Correct 58 ms 81932 KB Output is correct
15 Correct 58 ms 81940 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 81724 KB Output is correct
2 Correct 61 ms 81596 KB Output is correct
3 Correct 58 ms 81652 KB Output is correct
4 Correct 66 ms 81648 KB Output is correct
5 Correct 57 ms 81596 KB Output is correct
6 Correct 57 ms 81724 KB Output is correct
7 Correct 60 ms 81676 KB Output is correct
8 Correct 68 ms 81688 KB Output is correct
9 Correct 60 ms 81612 KB Output is correct
10 Correct 59 ms 81744 KB Output is correct
11 Correct 61 ms 81820 KB Output is correct
12 Correct 62 ms 81672 KB Output is correct
13 Correct 59 ms 81736 KB Output is correct
14 Correct 58 ms 81908 KB Output is correct
15 Correct 61 ms 81944 KB Output is correct
16 Correct 59 ms 81824 KB Output is correct
17 Correct 70 ms 82252 KB Output is correct
18 Correct 58 ms 81976 KB Output is correct
19 Correct 59 ms 81804 KB Output is correct
20 Correct 72 ms 81768 KB Output is correct
21 Correct 64 ms 81724 KB Output is correct
22 Correct 59 ms 81892 KB Output is correct
23 Correct 72 ms 81916 KB Output is correct
24 Correct 59 ms 82224 KB Output is correct
25 Correct 69 ms 81964 KB Output is correct
26 Correct 71 ms 82048 KB Output is correct
27 Correct 68 ms 81924 KB Output is correct
28 Correct 63 ms 82544 KB Output is correct
29 Correct 63 ms 84176 KB Output is correct
30 Correct 60 ms 82328 KB Output is correct
31 Correct 61 ms 82976 KB Output is correct
32 Correct 59 ms 82648 KB Output is correct
33 Correct 67 ms 86584 KB Output is correct
34 Correct 64 ms 86468 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 81608 KB Output is correct
2 Correct 68 ms 81720 KB Output is correct
3 Correct 60 ms 81708 KB Output is correct
4 Correct 58 ms 81692 KB Output is correct
5 Correct 72 ms 81676 KB Output is correct
6 Correct 64 ms 81696 KB Output is correct
7 Correct 59 ms 81708 KB Output is correct
8 Correct 67 ms 81604 KB Output is correct
9 Correct 62 ms 81736 KB Output is correct
10 Correct 61 ms 81728 KB Output is correct
11 Correct 62 ms 81932 KB Output is correct
12 Correct 62 ms 81696 KB Output is correct
13 Correct 61 ms 81640 KB Output is correct
14 Correct 60 ms 81828 KB Output is correct
15 Correct 60 ms 81944 KB Output is correct
16 Correct 62 ms 81756 KB Output is correct
17 Correct 71 ms 82192 KB Output is correct
18 Correct 59 ms 81956 KB Output is correct
19 Correct 59 ms 81836 KB Output is correct
20 Correct 58 ms 81728 KB Output is correct
21 Correct 73 ms 81700 KB Output is correct
22 Correct 65 ms 81912 KB Output is correct
23 Correct 62 ms 81968 KB Output is correct
24 Correct 63 ms 82168 KB Output is correct
25 Correct 68 ms 81944 KB Output is correct
26 Correct 73 ms 82124 KB Output is correct
27 Correct 60 ms 81944 KB Output is correct
28 Correct 64 ms 82524 KB Output is correct
29 Correct 72 ms 84084 KB Output is correct
30 Correct 66 ms 82380 KB Output is correct
31 Correct 69 ms 83000 KB Output is correct
32 Correct 71 ms 82656 KB Output is correct
33 Correct 64 ms 86440 KB Output is correct
34 Correct 64 ms 86460 KB Output is correct
35 Correct 66 ms 85680 KB Output is correct
36 Correct 62 ms 82368 KB Output is correct
37 Correct 74 ms 88868 KB Output is correct
38 Correct 70 ms 88020 KB Output is correct
39 Correct 82 ms 88096 KB Output is correct
40 Correct 70 ms 88080 KB Output is correct
41 Correct 69 ms 88104 KB Output is correct
42 Correct 65 ms 82348 KB Output is correct
43 Correct 68 ms 82252 KB Output is correct
44 Correct 63 ms 82144 KB Output is correct
45 Correct 119 ms 100716 KB Output is correct
46 Correct 91 ms 100776 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 81668 KB Output is correct
2 Correct 70 ms 81688 KB Output is correct
3 Correct 62 ms 81668 KB Output is correct
4 Correct 58 ms 81616 KB Output is correct
5 Correct 58 ms 81656 KB Output is correct
6 Correct 60 ms 81640 KB Output is correct
7 Correct 58 ms 81636 KB Output is correct
8 Correct 67 ms 81640 KB Output is correct
9 Correct 66 ms 81704 KB Output is correct
10 Correct 58 ms 81780 KB Output is correct
11 Correct 62 ms 81868 KB Output is correct
12 Correct 58 ms 81676 KB Output is correct
13 Correct 58 ms 81764 KB Output is correct
14 Correct 60 ms 81956 KB Output is correct
15 Correct 58 ms 81876 KB Output is correct
16 Correct 58 ms 81868 KB Output is correct
17 Correct 64 ms 82284 KB Output is correct
18 Correct 63 ms 81992 KB Output is correct
19 Correct 70 ms 81884 KB Output is correct
20 Correct 63 ms 81728 KB Output is correct
21 Correct 59 ms 81828 KB Output is correct
22 Correct 59 ms 81960 KB Output is correct
23 Correct 67 ms 81928 KB Output is correct
24 Correct 62 ms 82148 KB Output is correct
25 Correct 59 ms 81992 KB Output is correct
26 Correct 67 ms 82028 KB Output is correct
27 Correct 62 ms 81936 KB Output is correct
28 Correct 59 ms 82584 KB Output is correct
29 Correct 75 ms 84148 KB Output is correct
30 Correct 77 ms 82396 KB Output is correct
31 Correct 72 ms 83060 KB Output is correct
32 Correct 65 ms 82636 KB Output is correct
33 Correct 79 ms 86600 KB Output is correct
34 Correct 81 ms 86468 KB Output is correct
35 Correct 69 ms 85792 KB Output is correct
36 Correct 62 ms 82332 KB Output is correct
37 Correct 90 ms 88964 KB Output is correct
38 Correct 74 ms 88140 KB Output is correct
39 Correct 91 ms 88220 KB Output is correct
40 Correct 73 ms 88228 KB Output is correct
41 Correct 83 ms 88252 KB Output is correct
42 Correct 69 ms 82504 KB Output is correct
43 Correct 69 ms 82404 KB Output is correct
44 Correct 65 ms 82304 KB Output is correct
45 Correct 97 ms 100984 KB Output is correct
46 Correct 96 ms 100920 KB Output is correct
47 Correct 118 ms 111532 KB Output is correct
48 Correct 71 ms 91084 KB Output is correct
49 Correct 68 ms 87556 KB Output is correct
50 Correct 82 ms 87652 KB Output is correct
51 Correct 92 ms 94440 KB Output is correct
52 Correct 105 ms 95524 KB Output is correct
53 Correct 71 ms 85360 KB Output is correct
54 Correct 65 ms 83156 KB Output is correct
55 Correct 76 ms 84104 KB Output is correct
56 Correct 80 ms 83672 KB Output is correct
57 Correct 87 ms 99280 KB Output is correct
58 Correct 67 ms 85080 KB Output is correct
59 Correct 68 ms 86272 KB Output is correct
60 Correct 72 ms 87932 KB Output is correct
61 Correct 70 ms 86744 KB Output is correct
62 Correct 110 ms 101580 KB Output is correct
63 Correct 242 ms 173280 KB Output is correct
64 Correct 314 ms 194204 KB Output is correct
65 Correct 463 ms 243672 KB Output is correct
66 Runtime error 204 ms 262144 KB Execution killed with signal 11
67 Halted 0 ms 0 KB -