oj.uz

Submission #393639

# Submission time Handle Problem Language Result Execution time Memory
393639 2021-04-24T07:23:35 Z loctildore Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 395 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define x first
#define y second
#define elif else if
#define endl '\n'
#define all(x) begin(x), end(x)
template <typename T>
ostream& operator << (ostream& os, const vector<T>& a) {
    os << '[';
    bool E = false;
    for(const T& x : a) {
        if(E) os << ' ';
        os << x;
        E = true;
    }
    return os << ']';
}
int n,m;
int b[30069],p[30069];
vector<pair<int,int>> grph[301*30069];
int done[301*30069];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>m;
  for (int i = 1; i <= 300; i++) {
    for (int j = 0; j < n-i; j++) {
      grph[j+i*30069].push_back({1,j+i+i*30069});
      grph[j+i+i*30069].push_back({1,j+i*30069});
    }
    for (int j = 0; j < n; j++) {
      grph[j+i*30069].push_back({0,j});
    }
  }
  for (int i = 0; i < m; i++) {
    cin>>b[i]>>p[i];
    if (p[i]<=300) {
      grph[b[i]].push_back({0,b[i]+p[i]*30069});
    }
    else{
      for (int j = b[i]%p[i]; j < n; j+=p[i]) {
        grph[b[i]].push_back({abs(b[i]-j)/p[i],j});
      }
    }
  }
  pq.push({0,b[0]});
  while (pq.size()) {
    auto temp=pq.top();
    pq.pop();
    if (done[temp.s]) {
      continue;
    }
    done[temp.s]=true;
    if (temp.s==b[1]) {
      cout<<temp.f<<endl;
      return 0;
    }
    for (auto i : grph[temp.s]) {
      pq.push({temp.f+i.f,i.s});
    }
  }
  cout<<-1<<endl;
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 212976 KB Output is correct
2 Correct 124 ms 212964 KB Output is correct
3 Correct 121 ms 212844 KB Output is correct
4 Correct 122 ms 212916 KB Output is correct
5 Correct 120 ms 212940 KB Output is correct
6 Correct 121 ms 212876 KB Output is correct
7 Correct 118 ms 213044 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 212840 KB Output is correct
2 Correct 121 ms 212780 KB Output is correct
3 Correct 120 ms 212800 KB Output is correct
4 Correct 120 ms 212816 KB Output is correct
5 Correct 123 ms 212832 KB Output is correct
6 Correct 121 ms 212928 KB Output is correct
7 Correct 121 ms 212840 KB Output is correct
8 Correct 120 ms 213236 KB Output is correct
9 Correct 122 ms 213424 KB Output is correct
10 Correct 125 ms 214056 KB Output is correct
11 Correct 120 ms 213856 KB Output is correct
12 Correct 122 ms 213868 KB Output is correct
13 Correct 125 ms 213904 KB Output is correct
14 Correct 125 ms 214212 KB Output is correct
15 Correct 122 ms 214212 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 212928 KB Output is correct
2 Correct 119 ms 212848 KB Output is correct
3 Correct 121 ms 212800 KB Output is correct
4 Correct 121 ms 212916 KB Output is correct
5 Correct 120 ms 212960 KB Output is correct
6 Correct 120 ms 212848 KB Output is correct
7 Correct 124 ms 213052 KB Output is correct
8 Correct 121 ms 213140 KB Output is correct
9 Correct 121 ms 213444 KB Output is correct
10 Correct 122 ms 214056 KB Output is correct
11 Correct 120 ms 213960 KB Output is correct
12 Correct 120 ms 213948 KB Output is correct
13 Correct 121 ms 213900 KB Output is correct
14 Correct 124 ms 214232 KB Output is correct
15 Correct 124 ms 214212 KB Output is correct
16 Correct 125 ms 214984 KB Output is correct
17 Correct 145 ms 223436 KB Output is correct
18 Correct 186 ms 236076 KB Output is correct
19 Correct 198 ms 239640 KB Output is correct
20 Correct 198 ms 239792 KB Output is correct
21 Correct 133 ms 217156 KB Output is correct
22 Correct 186 ms 236608 KB Output is correct
23 Correct 184 ms 235008 KB Output is correct
24 Correct 201 ms 240068 KB Output is correct
25 Correct 197 ms 239696 KB Output is correct
26 Correct 211 ms 239940 KB Output is correct
27 Correct 208 ms 240468 KB Output is correct
28 Correct 201 ms 241220 KB Output is correct
29 Correct 217 ms 240180 KB Output is correct
30 Correct 202 ms 239884 KB Output is correct
31 Correct 204 ms 239924 KB Output is correct
32 Correct 202 ms 239940 KB Output is correct
33 Correct 237 ms 240568 KB Output is correct
34 Correct 216 ms 240328 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 213024 KB Output is correct
2 Correct 119 ms 212732 KB Output is correct
3 Correct 120 ms 212820 KB Output is correct
4 Correct 122 ms 212892 KB Output is correct
5 Correct 122 ms 212936 KB Output is correct
6 Correct 120 ms 212996 KB Output is correct
7 Correct 122 ms 212844 KB Output is correct
8 Correct 120 ms 213188 KB Output is correct
9 Correct 120 ms 213488 KB Output is correct
10 Correct 124 ms 214172 KB Output is correct
11 Correct 123 ms 213956 KB Output is correct
12 Correct 122 ms 213880 KB Output is correct
13 Correct 123 ms 213892 KB Output is correct
14 Correct 124 ms 214212 KB Output is correct
15 Correct 125 ms 214216 KB Output is correct
16 Correct 129 ms 214912 KB Output is correct
17 Correct 148 ms 223460 KB Output is correct
18 Correct 184 ms 236044 KB Output is correct
19 Correct 195 ms 239684 KB Output is correct
20 Correct 196 ms 239676 KB Output is correct
21 Correct 137 ms 217156 KB Output is correct
22 Correct 190 ms 236556 KB Output is correct
23 Correct 180 ms 235056 KB Output is correct
24 Correct 199 ms 240020 KB Output is correct
25 Correct 198 ms 239732 KB Output is correct
26 Correct 206 ms 239832 KB Output is correct
27 Correct 205 ms 240368 KB Output is correct
28 Correct 199 ms 241244 KB Output is correct
29 Correct 215 ms 240180 KB Output is correct
30 Correct 198 ms 239724 KB Output is correct
31 Correct 207 ms 239812 KB Output is correct
32 Correct 205 ms 239924 KB Output is correct
33 Correct 235 ms 240460 KB Output is correct
34 Correct 218 ms 240300 KB Output is correct
35 Correct 187 ms 235388 KB Output is correct
36 Correct 161 ms 227808 KB Output is correct
37 Correct 208 ms 241988 KB Output is correct
38 Correct 218 ms 243180 KB Output is correct
39 Correct 237 ms 240992 KB Output is correct
40 Correct 214 ms 241116 KB Output is correct
41 Correct 218 ms 242628 KB Output is correct
42 Correct 201 ms 240624 KB Output is correct
43 Correct 203 ms 241096 KB Output is correct
44 Correct 204 ms 240728 KB Output is correct
45 Correct 395 ms 244032 KB Output is correct
46 Correct 303 ms 243140 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 213044 KB Output is correct
2 Correct 119 ms 212788 KB Output is correct
3 Correct 120 ms 213028 KB Output is correct
4 Correct 120 ms 212860 KB Output is correct
5 Correct 119 ms 212932 KB Output is correct
6 Correct 119 ms 212924 KB Output is correct
7 Correct 119 ms 212864 KB Output is correct
8 Correct 121 ms 213188 KB Output is correct
9 Correct 122 ms 213572 KB Output is correct
10 Correct 125 ms 214244 KB Output is correct
11 Correct 122 ms 213904 KB Output is correct
12 Correct 128 ms 213840 KB Output is correct
13 Correct 125 ms 213828 KB Output is correct
14 Correct 126 ms 214212 KB Output is correct
15 Correct 126 ms 214212 KB Output is correct
16 Correct 126 ms 214880 KB Output is correct
17 Correct 145 ms 223428 KB Output is correct
18 Correct 186 ms 236140 KB Output is correct
19 Correct 200 ms 239684 KB Output is correct
20 Correct 201 ms 239700 KB Output is correct
21 Correct 135 ms 217284 KB Output is correct
22 Correct 188 ms 236556 KB Output is correct
23 Correct 182 ms 235076 KB Output is correct
24 Correct 200 ms 240112 KB Output is correct
25 Correct 199 ms 239756 KB Output is correct
26 Correct 207 ms 239780 KB Output is correct
27 Correct 205 ms 240452 KB Output is correct
28 Correct 201 ms 241220 KB Output is correct
29 Correct 214 ms 240068 KB Output is correct
30 Correct 207 ms 239788 KB Output is correct
31 Correct 207 ms 239940 KB Output is correct
32 Correct 204 ms 239776 KB Output is correct
33 Correct 248 ms 240580 KB Output is correct
34 Correct 220 ms 240452 KB Output is correct
35 Correct 188 ms 235484 KB Output is correct
36 Correct 160 ms 227568 KB Output is correct
37 Correct 210 ms 241984 KB Output is correct
38 Correct 218 ms 243280 KB Output is correct
39 Correct 211 ms 241060 KB Output is correct
40 Correct 218 ms 241268 KB Output is correct
41 Correct 218 ms 242752 KB Output is correct
42 Correct 202 ms 240524 KB Output is correct
43 Correct 205 ms 241240 KB Output is correct
44 Correct 202 ms 240776 KB Output is correct
45 Correct 388 ms 244000 KB Output is correct
46 Correct 307 ms 243296 KB Output is correct
47 Runtime error 242 ms 262148 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -