oj.uz

Submission #826513

# Submission time Handle Problem Language Result Execution time Memory
826513 2023-08-15T16:15:16 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 392 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
#define double long double
const int MAXN = 5e6 + 10;
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 b[m], p[m];
  for(int i=0; i<m; i++) cin >> b[i] >> p[i];
  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);
    }
  }
  for(int i=0; i<m; i++) {
    if(p[i] <= s) adj[b[i]].push_back((b[i]+p[i]*n) * 2 + 0);
    else {
      for(int j=b[i]%p[i]; j<n; j+=p[i]) {
        if(j+p[i] < n) adj[nxt + j/p[i]].push_back((nxt + j/p[i] + 1) * 2 + 1);
        if(j-p[i] >= 0) adj[nxt + j/p[i]].push_back((nxt + j/p[i] - 1) * 2 + 1);
        adj[nxt + j/p[i]].push_back(j * 2 + 0);
      }
      adj[b[i]].push_back((nxt + b[i]/p[i]) * 2 + 0);
      for(int j=b[i]%p[i]; j<n; j+=p[i]) {
        nxt++;
      }
    }
  }
  int k = nxt;
  int dist[k];
  bool vis[k];
  for(int i=0; i<k; i++) dist[i] = 1e9, vis[i] = 0;
  dist[b[0]] = 0;
  deque<int> dq;
  dq.push_back(b[0]);
  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[b[1]]==1e9?-1:dist[b[1]])<<"\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);
}
// 勿忘初衷

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 117708 KB Output is correct
2 Correct 59 ms 117720 KB Output is correct
3 Correct 55 ms 117656 KB Output is correct
4 Correct 55 ms 117652 KB Output is correct
5 Correct 56 ms 117660 KB Output is correct
6 Correct 56 ms 117720 KB Output is correct
7 Correct 56 ms 117680 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 117620 KB Output is correct
2 Correct 56 ms 117708 KB Output is correct
3 Correct 56 ms 117716 KB Output is correct
4 Correct 56 ms 117724 KB Output is correct
5 Correct 57 ms 117596 KB Output is correct
6 Correct 56 ms 117612 KB Output is correct
7 Correct 59 ms 117720 KB Output is correct
8 Correct 56 ms 117608 KB Output is correct
9 Correct 57 ms 117696 KB Output is correct
10 Correct 57 ms 117708 KB Output is correct
11 Correct 57 ms 117852 KB Output is correct
12 Correct 60 ms 117728 KB Output is correct
13 Correct 61 ms 117780 KB Output is correct
14 Correct 58 ms 117984 KB Output is correct
15 Correct 57 ms 117964 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 117688 KB Output is correct
2 Correct 60 ms 117628 KB Output is correct
3 Correct 57 ms 117648 KB Output is correct
4 Correct 57 ms 117716 KB Output is correct
5 Correct 56 ms 117608 KB Output is correct
6 Correct 57 ms 117784 KB Output is correct
7 Correct 57 ms 117708 KB Output is correct
8 Correct 57 ms 117696 KB Output is correct
9 Correct 57 ms 117692 KB Output is correct
10 Correct 56 ms 117748 KB Output is correct
11 Correct 57 ms 117880 KB Output is correct
12 Correct 57 ms 117752 KB Output is correct
13 Correct 56 ms 117792 KB Output is correct
14 Correct 56 ms 117984 KB Output is correct
15 Correct 57 ms 117920 KB Output is correct
16 Correct 60 ms 117920 KB Output is correct
17 Correct 63 ms 118768 KB Output is correct
18 Correct 66 ms 120484 KB Output is correct
19 Correct 65 ms 121000 KB Output is correct
20 Correct 64 ms 120892 KB Output is correct
21 Correct 62 ms 118032 KB Output is correct
22 Correct 64 ms 120564 KB Output is correct
23 Correct 70 ms 120136 KB Output is correct
24 Correct 66 ms 120908 KB Output is correct
25 Correct 69 ms 121036 KB Output is correct
26 Correct 66 ms 120988 KB Output is correct
27 Correct 67 ms 120884 KB Output is correct
28 Correct 68 ms 121324 KB Output is correct
29 Correct 73 ms 120992 KB Output is correct
30 Correct 65 ms 120908 KB Output is correct
31 Correct 65 ms 120992 KB Output is correct
32 Correct 68 ms 121244 KB Output is correct
33 Correct 71 ms 122244 KB Output is correct
34 Correct 71 ms 122344 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 117716 KB Output is correct
2 Correct 59 ms 117704 KB Output is correct
3 Correct 58 ms 117684 KB Output is correct
4 Correct 57 ms 117656 KB Output is correct
5 Correct 65 ms 117724 KB Output is correct
6 Correct 58 ms 117716 KB Output is correct
7 Correct 57 ms 117720 KB Output is correct
8 Correct 57 ms 117744 KB Output is correct
9 Correct 58 ms 117680 KB Output is correct
10 Correct 57 ms 117676 KB Output is correct
11 Correct 56 ms 117900 KB Output is correct
12 Correct 57 ms 117788 KB Output is correct
13 Correct 57 ms 117724 KB Output is correct
14 Correct 58 ms 117884 KB Output is correct
15 Correct 63 ms 117972 KB Output is correct
16 Correct 58 ms 117900 KB Output is correct
17 Correct 61 ms 118784 KB Output is correct
18 Correct 64 ms 120396 KB Output is correct
19 Correct 66 ms 120928 KB Output is correct
20 Correct 65 ms 120928 KB Output is correct
21 Correct 59 ms 118056 KB Output is correct
22 Correct 70 ms 120476 KB Output is correct
23 Correct 63 ms 120036 KB Output is correct
24 Correct 66 ms 120920 KB Output is correct
25 Correct 67 ms 121060 KB Output is correct
26 Correct 67 ms 121020 KB Output is correct
27 Correct 67 ms 120996 KB Output is correct
28 Correct 66 ms 121324 KB Output is correct
29 Correct 69 ms 120864 KB Output is correct
30 Correct 66 ms 120908 KB Output is correct
31 Correct 77 ms 120948 KB Output is correct
32 Correct 69 ms 121304 KB Output is correct
33 Correct 71 ms 122352 KB Output is correct
34 Correct 69 ms 122356 KB Output is correct
35 Correct 81 ms 122880 KB Output is correct
36 Correct 62 ms 119440 KB Output is correct
37 Correct 86 ms 125676 KB Output is correct
38 Correct 89 ms 125580 KB Output is correct
39 Correct 86 ms 125608 KB Output is correct
40 Correct 90 ms 125748 KB Output is correct
41 Correct 94 ms 125752 KB Output is correct
42 Correct 69 ms 121476 KB Output is correct
43 Correct 68 ms 121368 KB Output is correct
44 Correct 70 ms 121340 KB Output is correct
45 Correct 134 ms 136096 KB Output is correct
46 Correct 135 ms 136140 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 117720 KB Output is correct
2 Correct 58 ms 117696 KB Output is correct
3 Correct 57 ms 117660 KB Output is correct
4 Correct 57 ms 117716 KB Output is correct
5 Correct 57 ms 117724 KB Output is correct
6 Correct 57 ms 117668 KB Output is correct
7 Correct 66 ms 117668 KB Output is correct
8 Correct 59 ms 117700 KB Output is correct
9 Correct 59 ms 117704 KB Output is correct
10 Correct 63 ms 117784 KB Output is correct
11 Correct 68 ms 117848 KB Output is correct
12 Correct 58 ms 117688 KB Output is correct
13 Correct 57 ms 117712 KB Output is correct
14 Correct 57 ms 117916 KB Output is correct
15 Correct 64 ms 118048 KB Output is correct
16 Correct 58 ms 117856 KB Output is correct
17 Correct 61 ms 118748 KB Output is correct
18 Correct 65 ms 120392 KB Output is correct
19 Correct 65 ms 120904 KB Output is correct
20 Correct 69 ms 120908 KB Output is correct
21 Correct 57 ms 117964 KB Output is correct
22 Correct 70 ms 120520 KB Output is correct
23 Correct 73 ms 120140 KB Output is correct
24 Correct 77 ms 120908 KB Output is correct
25 Correct 66 ms 121056 KB Output is correct
26 Correct 66 ms 121060 KB Output is correct
27 Correct 67 ms 120912 KB Output is correct
28 Correct 66 ms 121332 KB Output is correct
29 Correct 73 ms 121044 KB Output is correct
30 Correct 68 ms 120836 KB Output is correct
31 Correct 66 ms 120996 KB Output is correct
32 Correct 67 ms 121352 KB Output is correct
33 Correct 86 ms 122360 KB Output is correct
34 Correct 72 ms 122272 KB Output is correct
35 Correct 76 ms 122816 KB Output is correct
36 Correct 64 ms 119492 KB Output is correct
37 Correct 91 ms 125756 KB Output is correct
38 Correct 88 ms 125624 KB Output is correct
39 Correct 87 ms 125660 KB Output is correct
40 Correct 90 ms 125704 KB Output is correct
41 Correct 110 ms 125656 KB Output is correct
42 Correct 69 ms 121460 KB Output is correct
43 Correct 69 ms 121328 KB Output is correct
44 Correct 71 ms 121288 KB Output is correct
45 Correct 135 ms 136092 KB Output is correct
46 Correct 147 ms 136164 KB Output is correct
47 Correct 344 ms 182196 KB Output is correct
48 Correct 385 ms 250692 KB Output is correct
49 Runtime error 392 ms 262144 KB Execution killed with signal 9
50 Halted 0 ms 0 KB -