oj.uz

Submission #826495

# Submission time Handle Problem Language Result Execution time Memory
826495 2023-08-15T15:58:24 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 133 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long 
#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 111 ms 258616 KB Output is correct
2 Correct 109 ms 258520 KB Output is correct
3 Correct 108 ms 258604 KB Output is correct
4 Correct 106 ms 258508 KB Output is correct
5 Correct 108 ms 258568 KB Output is correct
6 Correct 122 ms 258624 KB Output is correct
7 Correct 117 ms 258584 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 258508 KB Output is correct
2 Correct 105 ms 258512 KB Output is correct
3 Correct 107 ms 258620 KB Output is correct
4 Correct 107 ms 258540 KB Output is correct
5 Correct 107 ms 258512 KB Output is correct
6 Correct 121 ms 258556 KB Output is correct
7 Correct 110 ms 258624 KB Output is correct
8 Correct 109 ms 258636 KB Output is correct
9 Correct 110 ms 258560 KB Output is correct
10 Correct 109 ms 258692 KB Output is correct
11 Correct 121 ms 259036 KB Output is correct
12 Correct 115 ms 258740 KB Output is correct
13 Correct 114 ms 258792 KB Output is correct
14 Correct 113 ms 259140 KB Output is correct
15 Correct 113 ms 259036 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 258512 KB Output is correct
2 Correct 118 ms 258616 KB Output is correct
3 Correct 115 ms 258556 KB Output is correct
4 Correct 121 ms 258540 KB Output is correct
5 Correct 115 ms 258612 KB Output is correct
6 Correct 111 ms 258540 KB Output is correct
7 Correct 110 ms 258512 KB Output is correct
8 Correct 112 ms 258620 KB Output is correct
9 Correct 113 ms 258664 KB Output is correct
10 Correct 115 ms 258724 KB Output is correct
11 Correct 111 ms 259032 KB Output is correct
12 Correct 124 ms 258812 KB Output is correct
13 Correct 108 ms 258764 KB Output is correct
14 Correct 119 ms 259140 KB Output is correct
15 Correct 121 ms 259136 KB Output is correct
16 Correct 130 ms 259040 KB Output is correct
17 Correct 125 ms 261008 KB Output is correct
18 Runtime error 97 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 111 ms 258620 KB Output is correct
2 Correct 120 ms 258500 KB Output is correct
3 Correct 130 ms 258588 KB Output is correct
4 Correct 126 ms 258620 KB Output is correct
5 Correct 127 ms 258660 KB Output is correct
6 Correct 111 ms 258584 KB Output is correct
7 Correct 108 ms 258524 KB Output is correct
8 Correct 107 ms 258552 KB Output is correct
9 Correct 108 ms 258624 KB Output is correct
10 Correct 133 ms 258724 KB Output is correct
11 Correct 118 ms 259044 KB Output is correct
12 Correct 117 ms 258716 KB Output is correct
13 Correct 117 ms 258812 KB Output is correct
14 Correct 116 ms 259140 KB Output is correct
15 Correct 112 ms 259048 KB Output is correct
16 Correct 114 ms 259060 KB Output is correct
17 Correct 118 ms 260976 KB Output is correct
18 Runtime error 96 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 127 ms 258616 KB Output is correct
2 Correct 121 ms 258648 KB Output is correct
3 Correct 119 ms 258524 KB Output is correct
4 Correct 111 ms 258508 KB Output is correct
5 Correct 118 ms 258496 KB Output is correct
6 Correct 124 ms 258660 KB Output is correct
7 Correct 124 ms 258512 KB Output is correct
8 Correct 123 ms 258592 KB Output is correct
9 Correct 116 ms 258660 KB Output is correct
10 Correct 111 ms 258764 KB Output is correct
11 Correct 118 ms 259020 KB Output is correct
12 Correct 122 ms 258720 KB Output is correct
13 Correct 130 ms 258684 KB Output is correct
14 Correct 118 ms 259112 KB Output is correct
15 Correct 120 ms 259256 KB Output is correct
16 Correct 111 ms 259020 KB Output is correct
17 Correct 116 ms 261000 KB Output is correct
18 Runtime error 103 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -