oj.uz

답안 #1009726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009726 2024-06-28T01:27:46 Z asdfgrace Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 247 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*
can jump only multiples of 1 number
get from p0 to p1
can only jump if 0 or it was passed to you
everyone will only have it once?
can add o(m^2) edges and run dijkstra
alternatively, can add o(n^2) edges
*/

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(m);
  vector<vector<array<int, 2>>> edges(n);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    if (b[i] != 0) {
      for (int j = a[i] + b[i]; j < n; j += b[i]) {
        edges[a[i]].push_back({j, (j - a[i]) / b[i]});
      }
      for (int j = a[i] - b[i]; j >= 0; j -= b[i]) {
        edges[a[i]].push_back({j, (a[i] - j) / b[i]});
      }
    }
  }
  priority_queue<array<int, 2>> q;
  vector<int> dist(n, 1e9);
  dist[a[0]] = 0;
  q.push({0, a[0]});
  while (q.size()) {
    int d = -q.top()[0], node = q.top()[1];
    q.pop();
    if (d != dist[node]) continue;
    for (auto [next, wt] : edges[node]) {
      if (dist[node] + wt < dist[next]) {
        dist[next] = dist[node] + wt;
        q.push({-dist[next], next});
      }
    }
  }
  cout << (dist[a[1]] == 1e9 ? -1 : dist[a[1]]) << '\n';
}

/*
any observations help

check every line
IF YOUR LINES AREN'T WRONG
CHECK IF YOUR LINES ARE IN THE RIGHT ORDER

NEVER GIVE UP
*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 372 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 352 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 3 ms 2512 KB Output is correct
13 Correct 4 ms 2528 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 3 ms 2516 KB Output is correct
13 Correct 3 ms 2528 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 45 ms 32536 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 40 ms 34120 KB Output is correct
27 Correct 34 ms 33712 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 2 ms 1116 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 860 KB Output is correct
33 Correct 3 ms 1884 KB Output is correct
34 Correct 4 ms 1912 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 2512 KB Output is correct
13 Correct 3 ms 2528 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 45 ms 32612 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 36 ms 33980 KB Output is correct
27 Correct 35 ms 33708 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 2 ms 1116 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 696 KB Output is correct
33 Correct 3 ms 1884 KB Output is correct
34 Correct 3 ms 1884 KB Output is correct
35 Correct 5 ms 2140 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 7 ms 3932 KB Output is correct
38 Correct 7 ms 3164 KB Output is correct
39 Correct 8 ms 3404 KB Output is correct
40 Correct 7 ms 3420 KB Output is correct
41 Correct 8 ms 3320 KB Output is correct
42 Runtime error 247 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 2512 KB Output is correct
13 Correct 3 ms 2528 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 416 KB Output is correct
20 Correct 46 ms 32628 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 37 ms 34120 KB Output is correct
27 Correct 32 ms 33456 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 2 ms 1116 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 696 KB Output is correct
33 Correct 3 ms 1884 KB Output is correct
34 Correct 3 ms 1884 KB Output is correct
35 Correct 5 ms 2292 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 9 ms 3888 KB Output is correct
38 Correct 7 ms 3164 KB Output is correct
39 Correct 10 ms 3420 KB Output is correct
40 Correct 8 ms 3228 KB Output is correct
41 Correct 6 ms 3164 KB Output is correct
42 Runtime error 219 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -