답안 #1009723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009723	2024-06-28T01:21:53 Z	asdfgrace	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	243 ms	262144 KB

skyscraper

#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];
    for (int j = a[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({a[0], 0});
  while (q.size()) {
    int node = q.top()[0], d = -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({next, -dist[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	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	456 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct

Subtask #2
12.0 / 12.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	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	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	456 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	3 ms	2436 KB	Output is correct
13	Correct	3 ms	2644 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	388 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	3 ms	2516 KB	Output is correct
13	Correct	3 ms	2644 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 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	464 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	44 ms	32428 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	604 KB	Output is correct
24	Correct	3 ms	860 KB	Output is correct
25	Correct	1 ms	612 KB	Output is correct
26	Correct	39 ms	33984 KB	Output is correct
27	Correct	36 ms	34240 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	756 KB	Output is correct
33	Correct	3 ms	1884 KB	Output is correct
34	Correct	3 ms	1880 KB	Output is correct

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 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	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	4 ms	2512 KB	Output is correct
13	Correct	3 ms	2528 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	2 ms	600 KB	Output is correct
18	Correct	0 ms	600 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	43 ms	32600 KB	Output is correct
21	Correct	0 ms	344 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	2 ms	600 KB	Output is correct
25	Correct	1 ms	604 KB	Output is correct
26	Correct	37 ms	33472 KB	Output is correct
27	Correct	35 ms	33716 KB	Output is correct
28	Correct	1 ms	600 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	604 KB	Output is correct
33	Correct	3 ms	1884 KB	Output is correct
34	Correct	4 ms	1744 KB	Output is correct
35	Correct	11 ms	2984 KB	Output is correct
36	Correct	3 ms	880 KB	Output is correct
37	Correct	10 ms	4416 KB	Output is correct
38	Correct	11 ms	4060 KB	Output is correct
39	Correct	11 ms	4188 KB	Output is correct
40	Correct	9 ms	4152 KB	Output is correct
41	Correct	10 ms	3928 KB	Output is correct
42	Runtime error	242 ms	262144 KB	Execution killed with signal 9
43	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.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	1 ms	348 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	600 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	604 KB	Output is correct
12	Correct	4 ms	2512 KB	Output is correct
13	Correct	3 ms	2528 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	456 KB	Output is correct
17	Correct	2 ms	600 KB	Output is correct
18	Correct	1 ms	576 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	44 ms	32604 KB	Output is correct
21	Correct	0 ms	344 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	3 ms	604 KB	Output is correct
25	Correct	1 ms	604 KB	Output is correct
26	Correct	37 ms	34800 KB	Output is correct
27	Correct	37 ms	33480 KB	Output is correct
28	Correct	1 ms	604 KB	Output is correct
29	Correct	2 ms	1132 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	604 KB	Output is correct
33	Correct	3 ms	1884 KB	Output is correct
34	Correct	3 ms	1880 KB	Output is correct
35	Correct	10 ms	2772 KB	Output is correct
36	Correct	2 ms	860 KB	Output is correct
37	Correct	11 ms	4444 KB	Output is correct
38	Correct	9 ms	3932 KB	Output is correct
39	Correct	10 ms	4188 KB	Output is correct
40	Correct	10 ms	4124 KB	Output is correct
41	Correct	9 ms	3932 KB	Output is correct
42	Runtime error	243 ms	262144 KB	Execution killed with signal 9
43	Halted	0 ms	0 KB	-

답안 #1009723

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
0 / 21.0

Subtask #5
0 / 43.0