답안 #1009736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009736	2024-06-28T02:13:41 Z	asdfgrace	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	133 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<int>> w(n, vector<int>(n, 1e9));
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    for (int j = a[i] + b[i]; j < n; j += b[i]) {
      w[a[i]][j] = min(w[a[i]][j], (j - a[i]) / b[i]);
    }
    for (int j = a[i] - b[i]; j >= 0; j -= b[i]) {
      w[a[i]][j] = min(w[a[i]][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 (int next = 0; next < n; next++) {
      int wt = w[node][next];
      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	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 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	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	1 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	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	600 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	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 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	604 KB	Output is correct
17	Correct	3 ms	2652 KB	Output is correct
18	Correct	5 ms	12380 KB	Output is correct
19	Correct	6 ms	15952 KB	Output is correct
20	Correct	18 ms	16216 KB	Output is correct
21	Correct	1 ms	860 KB	Output is correct
22	Correct	5 ms	12892 KB	Output is correct
23	Correct	7 ms	10332 KB	Output is correct
24	Correct	10 ms	14684 KB	Output is correct
25	Correct	12 ms	16220 KB	Output is correct
26	Correct	17 ms	16212 KB	Output is correct
27	Correct	17 ms	16220 KB	Output is correct
28	Correct	11 ms	15984 KB	Output is correct
29	Correct	11 ms	16220 KB	Output is correct
30	Correct	11 ms	16220 KB	Output is correct
31	Correct	11 ms	16220 KB	Output is correct
32	Correct	11 ms	16220 KB	Output is correct
33	Correct	13 ms	16284 KB	Output is correct
34	Correct	11 ms	16220 KB	Output is correct

Subtask #4
21.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	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	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 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	604 KB	Output is correct
17	Correct	2 ms	2652 KB	Output is correct
18	Correct	5 ms	12380 KB	Output is correct
19	Correct	6 ms	15964 KB	Output is correct
20	Correct	18 ms	16220 KB	Output is correct
21	Correct	1 ms	860 KB	Output is correct
22	Correct	5 ms	12828 KB	Output is correct
23	Correct	7 ms	10332 KB	Output is correct
24	Correct	14 ms	14684 KB	Output is correct
25	Correct	11 ms	16220 KB	Output is correct
26	Correct	18 ms	16220 KB	Output is correct
27	Correct	17 ms	16216 KB	Output is correct
28	Correct	11 ms	15964 KB	Output is correct
29	Correct	11 ms	16312 KB	Output is correct
30	Correct	11 ms	16220 KB	Output is correct
31	Correct	16 ms	16268 KB	Output is correct
32	Correct	10 ms	16220 KB	Output is correct
33	Correct	11 ms	16220 KB	Output is correct
34	Correct	11 ms	16220 KB	Output is correct
35	Correct	10 ms	8796 KB	Output is correct
36	Correct	6 ms	5212 KB	Output is correct
37	Correct	16 ms	15452 KB	Output is correct
38	Correct	17 ms	16476 KB	Output is correct
39	Correct	19 ms	16476 KB	Output is correct
40	Correct	18 ms	16476 KB	Output is correct
41	Correct	17 ms	16476 KB	Output is correct
42	Correct	131 ms	16456 KB	Output is correct
43	Correct	124 ms	16472 KB	Output is correct
44	Correct	133 ms	16620 KB	Output is correct
45	Correct	20 ms	16476 KB	Output is correct
46	Correct	15 ms	16476 KB	Output is correct

Subtask #5
0 / 43.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	0 ms	384 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	1 ms	348 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	1 ms	604 KB	Output is correct
17	Correct	2 ms	2652 KB	Output is correct
18	Correct	5 ms	12380 KB	Output is correct
19	Correct	5 ms	16124 KB	Output is correct
20	Correct	17 ms	16216 KB	Output is correct
21	Correct	1 ms	856 KB	Output is correct
22	Correct	5 ms	12892 KB	Output is correct
23	Correct	7 ms	10424 KB	Output is correct
24	Correct	8 ms	14684 KB	Output is correct
25	Correct	9 ms	16212 KB	Output is correct
26	Correct	16 ms	16216 KB	Output is correct
27	Correct	16 ms	16216 KB	Output is correct
28	Correct	10 ms	15964 KB	Output is correct
29	Correct	12 ms	16220 KB	Output is correct
30	Correct	10 ms	16220 KB	Output is correct
31	Correct	11 ms	16100 KB	Output is correct
32	Correct	12 ms	16020 KB	Output is correct
33	Correct	11 ms	16220 KB	Output is correct
34	Correct	10 ms	16268 KB	Output is correct
35	Correct	8 ms	8796 KB	Output is correct
36	Correct	4 ms	5212 KB	Output is correct
37	Correct	12 ms	15484 KB	Output is correct
38	Correct	17 ms	16476 KB	Output is correct
39	Correct	15 ms	16472 KB	Output is correct
40	Correct	15 ms	16476 KB	Output is correct
41	Correct	15 ms	16476 KB	Output is correct
42	Correct	118 ms	16612 KB	Output is correct
43	Correct	117 ms	16616 KB	Output is correct
44	Correct	113 ms	16476 KB	Output is correct
45	Correct	14 ms	16472 KB	Output is correct
46	Correct	16 ms	16472 KB	Output is correct
47	Runtime error	113 ms	262144 KB	Execution killed with signal 9
48	Halted	0 ms	0 KB	-

답안 #1009736

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.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
21.0 / 21.0

Subtask #5
0 / 43.0