oj.uz

Submission #826647

# Submission time Handle Problem Language Result Execution time Memory
826647 2023-08-15T18:59:08 Z cig32 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 490 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;
  unordered_map<int, int> bruh[30001];
  for(int i=0; i<m; i++) {
    int b, p;
    cin >> b >> p;
    if(i == 0) st = b;
    if(i == 1) en = b;
    if(!bruh[p].count(b%p)) {
      bruh[p][b%p] = nxt;
      construct(b, p);
    }
    else {
      add_command(b, (bruh[p][b%p] + b/p) * 2);
    }
  }
  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];
  bitset<MAXN2> vis;
  //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:98:17: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |   cout<<(dist[en]==1e9?-1:dist[en])<<"\n";
      |          ~~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 84628 KB Output is correct
2 Correct 61 ms 84576 KB Output is correct
3 Correct 63 ms 84720 KB Output is correct
4 Correct 59 ms 84580 KB Output is correct
5 Correct 59 ms 84564 KB Output is correct
6 Correct 61 ms 84584 KB Output is correct
7 Correct 60 ms 84548 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 84588 KB Output is correct
2 Correct 60 ms 84556 KB Output is correct
3 Correct 60 ms 84532 KB Output is correct
4 Correct 61 ms 84532 KB Output is correct
5 Correct 60 ms 84608 KB Output is correct
6 Correct 59 ms 84588 KB Output is correct
7 Correct 59 ms 84604 KB Output is correct
8 Correct 60 ms 84608 KB Output is correct
9 Correct 60 ms 84556 KB Output is correct
10 Correct 59 ms 84596 KB Output is correct
11 Correct 58 ms 84784 KB Output is correct
12 Correct 58 ms 84604 KB Output is correct
13 Correct 65 ms 84648 KB Output is correct
14 Correct 60 ms 84896 KB Output is correct
15 Correct 60 ms 84904 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 84624 KB Output is correct
2 Correct 58 ms 84520 KB Output is correct
3 Correct 60 ms 84568 KB Output is correct
4 Correct 59 ms 84620 KB Output is correct
5 Correct 59 ms 84544 KB Output is correct
6 Correct 60 ms 84608 KB Output is correct
7 Correct 59 ms 84632 KB Output is correct
8 Correct 60 ms 84552 KB Output is correct
9 Correct 59 ms 84632 KB Output is correct
10 Correct 59 ms 84692 KB Output is correct
11 Correct 69 ms 84756 KB Output is correct
12 Correct 59 ms 84556 KB Output is correct
13 Correct 65 ms 84656 KB Output is correct
14 Correct 60 ms 84864 KB Output is correct
15 Correct 61 ms 84824 KB Output is correct
16 Correct 65 ms 84828 KB Output is correct
17 Correct 62 ms 85276 KB Output is correct
18 Correct 60 ms 84956 KB Output is correct
19 Correct 62 ms 84836 KB Output is correct
20 Correct 59 ms 84736 KB Output is correct
21 Correct 59 ms 84848 KB Output is correct
22 Correct 60 ms 84916 KB Output is correct
23 Correct 61 ms 84992 KB Output is correct
24 Correct 60 ms 85292 KB Output is correct
25 Correct 61 ms 85092 KB Output is correct
26 Correct 59 ms 84928 KB Output is correct
27 Correct 60 ms 84940 KB Output is correct
28 Correct 61 ms 85604 KB Output is correct
29 Correct 65 ms 86988 KB Output is correct
30 Correct 60 ms 85324 KB Output is correct
31 Correct 60 ms 85904 KB Output is correct
32 Correct 60 ms 85528 KB Output is correct
33 Correct 68 ms 89364 KB Output is correct
34 Correct 64 ms 89352 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 84548 KB Output is correct
2 Correct 62 ms 84568 KB Output is correct
3 Correct 59 ms 84556 KB Output is correct
4 Correct 59 ms 84564 KB Output is correct
5 Correct 59 ms 84572 KB Output is correct
6 Correct 58 ms 84536 KB Output is correct
7 Correct 59 ms 84636 KB Output is correct
8 Correct 63 ms 84644 KB Output is correct
9 Correct 60 ms 84556 KB Output is correct
10 Correct 59 ms 84624 KB Output is correct
11 Correct 61 ms 84860 KB Output is correct
12 Correct 60 ms 84592 KB Output is correct
13 Correct 59 ms 84612 KB Output is correct
14 Correct 60 ms 84940 KB Output is correct
15 Correct 60 ms 84940 KB Output is correct
16 Correct 60 ms 84812 KB Output is correct
17 Correct 66 ms 85268 KB Output is correct
18 Correct 59 ms 84992 KB Output is correct
19 Correct 59 ms 84832 KB Output is correct
20 Correct 60 ms 84684 KB Output is correct
21 Correct 58 ms 84832 KB Output is correct
22 Correct 59 ms 84856 KB Output is correct
23 Correct 63 ms 84932 KB Output is correct
24 Correct 60 ms 85208 KB Output is correct
25 Correct 61 ms 85044 KB Output is correct
26 Correct 60 ms 84936 KB Output is correct
27 Correct 60 ms 84920 KB Output is correct
28 Correct 61 ms 85580 KB Output is correct
29 Correct 61 ms 87036 KB Output is correct
30 Correct 61 ms 85280 KB Output is correct
31 Correct 60 ms 85964 KB Output is correct
32 Correct 60 ms 85548 KB Output is correct
33 Correct 66 ms 89328 KB Output is correct
34 Correct 66 ms 89348 KB Output is correct
35 Correct 72 ms 89476 KB Output is correct
36 Correct 61 ms 85548 KB Output is correct
37 Correct 73 ms 92036 KB Output is correct
38 Correct 75 ms 92028 KB Output is correct
39 Correct 76 ms 91964 KB Output is correct
40 Correct 75 ms 91932 KB Output is correct
41 Correct 76 ms 91908 KB Output is correct
42 Correct 62 ms 85196 KB Output is correct
43 Correct 64 ms 85216 KB Output is correct
44 Correct 68 ms 85068 KB Output is correct
45 Correct 96 ms 104520 KB Output is correct
46 Correct 96 ms 104452 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 84608 KB Output is correct
2 Correct 59 ms 84584 KB Output is correct
3 Correct 62 ms 84584 KB Output is correct
4 Correct 64 ms 84532 KB Output is correct
5 Correct 59 ms 84556 KB Output is correct
6 Correct 58 ms 84512 KB Output is correct
7 Correct 60 ms 84600 KB Output is correct
8 Correct 59 ms 84540 KB Output is correct
9 Correct 60 ms 84648 KB Output is correct
10 Correct 61 ms 84716 KB Output is correct
11 Correct 60 ms 84780 KB Output is correct
12 Correct 59 ms 84592 KB Output is correct
13 Correct 60 ms 84712 KB Output is correct
14 Correct 60 ms 84896 KB Output is correct
15 Correct 59 ms 84912 KB Output is correct
16 Correct 63 ms 84908 KB Output is correct
17 Correct 61 ms 85200 KB Output is correct
18 Correct 60 ms 84896 KB Output is correct
19 Correct 60 ms 84840 KB Output is correct
20 Correct 59 ms 84744 KB Output is correct
21 Correct 64 ms 84744 KB Output is correct
22 Correct 62 ms 84952 KB Output is correct
23 Correct 60 ms 84968 KB Output is correct
24 Correct 60 ms 85196 KB Output is correct
25 Correct 60 ms 85100 KB Output is correct
26 Correct 59 ms 84940 KB Output is correct
27 Correct 59 ms 84904 KB Output is correct
28 Correct 61 ms 85524 KB Output is correct
29 Correct 64 ms 87044 KB Output is correct
30 Correct 60 ms 85328 KB Output is correct
31 Correct 62 ms 85864 KB Output is correct
32 Correct 60 ms 85472 KB Output is correct
33 Correct 66 ms 89292 KB Output is correct
34 Correct 68 ms 89476 KB Output is correct
35 Correct 71 ms 89480 KB Output is correct
36 Correct 61 ms 85624 KB Output is correct
37 Correct 75 ms 91980 KB Output is correct
38 Correct 87 ms 92032 KB Output is correct
39 Correct 77 ms 91912 KB Output is correct
40 Correct 77 ms 91968 KB Output is correct
41 Correct 76 ms 91976 KB Output is correct
42 Correct 64 ms 85284 KB Output is correct
43 Correct 64 ms 85196 KB Output is correct
44 Correct 63 ms 84956 KB Output is correct
45 Correct 108 ms 104592 KB Output is correct
46 Correct 96 ms 104460 KB Output is correct
47 Correct 119 ms 114408 KB Output is correct
48 Correct 75 ms 95864 KB Output is correct
49 Correct 81 ms 92364 KB Output is correct
50 Correct 78 ms 91896 KB Output is correct
51 Correct 98 ms 99740 KB Output is correct
52 Correct 92 ms 100980 KB Output is correct
53 Correct 85 ms 89368 KB Output is correct
54 Correct 62 ms 85928 KB Output is correct
55 Correct 63 ms 86892 KB Output is correct
56 Correct 66 ms 86220 KB Output is correct
57 Correct 89 ms 101844 KB Output is correct
58 Correct 68 ms 87672 KB Output is correct
59 Correct 70 ms 88780 KB Output is correct
60 Correct 77 ms 89884 KB Output is correct
61 Correct 69 ms 89664 KB Output is correct
62 Correct 93 ms 105056 KB Output is correct
63 Correct 241 ms 174880 KB Output is correct
64 Correct 289 ms 195436 KB Output is correct
65 Correct 490 ms 243532 KB Output is correct
66 Runtime error 215 ms 262144 KB Execution killed with signal 11
67 Halted 0 ms 0 KB -