oj.uz

Submission #826496

# Submission time Handle Problem Language Result Execution time Memory
826496 2023-08-15T15:59:07 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 139 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
#define double long double
const int MAXN = 1e5 + 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<pair<int, int> >adj[11000000];
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, 1});
      if(j-i >= i*n) adj[j].push_back({j-i, 1});
      adj[j].push_back({j%n, 0});
    }
  }
  for(int i=0; i<m; i++) {
    if(p[i] <= s) adj[b[i]].push_back({b[i]+p[i]*n, 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, 1});
        if(j-p[i] >= 0) adj[nxt + j/p[i]].push_back({nxt + j/p[i] - 1, 1});
        adj[nxt + j/p[i]].push_back({j, 0});
      }
      adj[b[i]].push_back({nxt + b[i]/p[i], 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(pair<int, int> x: adj[f]) {
        if(!vis[x.first] && dist[x.first] > dist[f] + x.second) {
          dist[x.first] = dist[f] + x.second;
          if(x.second == 0) dq.push_front(x.first);
          else dq.push_back(x.first);
        }
      }
    }
  }
  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 113 ms 258632 KB Output is correct
2 Correct 113 ms 258612 KB Output is correct
3 Correct 121 ms 258692 KB Output is correct
4 Correct 109 ms 258512 KB Output is correct
5 Correct 117 ms 258568 KB Output is correct
6 Correct 117 ms 258528 KB Output is correct
7 Correct 125 ms 258616 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 258532 KB Output is correct
2 Correct 115 ms 258540 KB Output is correct
3 Correct 118 ms 258508 KB Output is correct
4 Correct 123 ms 258500 KB Output is correct
5 Correct 126 ms 258536 KB Output is correct
6 Correct 122 ms 258528 KB Output is correct
7 Correct 118 ms 258568 KB Output is correct
8 Correct 127 ms 258576 KB Output is correct
9 Correct 120 ms 258600 KB Output is correct
10 Correct 122 ms 258716 KB Output is correct
11 Correct 117 ms 258888 KB Output is correct
12 Correct 118 ms 258708 KB Output is correct
13 Correct 123 ms 258712 KB Output is correct
14 Correct 115 ms 258928 KB Output is correct
15 Correct 115 ms 258808 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 258572 KB Output is correct
2 Correct 119 ms 258564 KB Output is correct
3 Correct 136 ms 258616 KB Output is correct
4 Correct 128 ms 258612 KB Output is correct
5 Correct 126 ms 258616 KB Output is correct
6 Correct 121 ms 258616 KB Output is correct
7 Correct 126 ms 258516 KB Output is correct
8 Correct 127 ms 258552 KB Output is correct
9 Correct 115 ms 258628 KB Output is correct
10 Correct 120 ms 258716 KB Output is correct
11 Correct 123 ms 258900 KB Output is correct
12 Correct 134 ms 258704 KB Output is correct
13 Correct 125 ms 258800 KB Output is correct
14 Correct 117 ms 258924 KB Output is correct
15 Correct 126 ms 258920 KB Output is correct
16 Correct 113 ms 258876 KB Output is correct
17 Correct 131 ms 259972 KB Output is correct
18 Runtime error 100 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 258528 KB Output is correct
2 Correct 117 ms 258616 KB Output is correct
3 Correct 115 ms 258500 KB Output is correct
4 Correct 118 ms 258608 KB Output is correct
5 Correct 121 ms 258544 KB Output is correct
6 Correct 131 ms 258620 KB Output is correct
7 Correct 128 ms 258616 KB Output is correct
8 Correct 118 ms 258628 KB Output is correct
9 Correct 131 ms 258624 KB Output is correct
10 Correct 121 ms 258604 KB Output is correct
11 Correct 125 ms 258856 KB Output is correct
12 Correct 121 ms 258648 KB Output is correct
13 Correct 116 ms 258640 KB Output is correct
14 Correct 123 ms 258884 KB Output is correct
15 Correct 127 ms 258872 KB Output is correct
16 Correct 118 ms 258788 KB Output is correct
17 Correct 124 ms 260020 KB Output is correct
18 Runtime error 103 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 258620 KB Output is correct
2 Correct 123 ms 258560 KB Output is correct
3 Correct 127 ms 258600 KB Output is correct
4 Correct 135 ms 258604 KB Output is correct
5 Correct 118 ms 258620 KB Output is correct
6 Correct 119 ms 258560 KB Output is correct
7 Correct 136 ms 258580 KB Output is correct
8 Correct 132 ms 258584 KB Output is correct
9 Correct 122 ms 258640 KB Output is correct
10 Correct 139 ms 258836 KB Output is correct
11 Correct 124 ms 258796 KB Output is correct
12 Correct 125 ms 258696 KB Output is correct
13 Correct 118 ms 258684 KB Output is correct
14 Correct 128 ms 258920 KB Output is correct
15 Correct 135 ms 258896 KB Output is correct
16 Correct 119 ms 258884 KB Output is correct
17 Correct 124 ms 260008 KB Output is correct
18 Runtime error 102 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -