답안 #766357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766357	2023-06-25T14:39:54 Z	linkret	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	87 ms	32852 KB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//const int N = 3e4 + 30, B = 175;
const int N = 2020;
const int inf = 2e9;

vector<int> g[N];
int n, m;
//int dist[N][B];
int dist[N][N];
bool bio[N];

/*
5 3
0 2
1 1
4 1
*/

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
        //for(int j = 0; j < B; j++) {
            dist[i][j] = inf;
        }
    }

    cin >> n >> m;

    int s = 0, f = 0;
    for(int i = 0; i < m; i++) {
        int x, k;
        cin >> x >> k;
        g[x].push_back(k);

        if(i == 0) s = x;
        if(i == 1) f = x;
    }

    priority_queue<array<int,3>> pq;

    for(auto x : g[s]) {
//        if(x < B) {
            dist[s][x] = 0;
            pq.push({dist[s][x], s, x});
//        } else {
//            for(int k = 1; s + k * x < N; k++) {
//                dist[s + k * x][0] = k;
//                pq.push({-dist[s + k * x][0], s + k * x, 0});
//            }
//
//            for(int k = 1; s - k * x >= 0; k++) {
//                dist[s - k * x][0] = k;
//                pq.push({-dist[s - k * x][0], s - k * x, 0});
//            }
//        }
    }
    bio[s] = 1;

    while(!pq.empty()) {
        auto top = pq.top();
        int d = get<0>(top);
        int v = get<1>(top);
        int p = get<2>(top);
        pq.pop();
        d = -d;

        if(d > dist[v][p]) continue;

        if(!bio[v]) {
              for(auto x : g[v]) {
//                    if(x < B) {
                          dist[v][x] = d;
                          pq.push({-dist[v][x], v, x});
//                    } else {
//                          for(int k = 1; v + k * x < n; k++) {
//                                if(dist[v + k * x][0] > d + k) {
//                                      dist[v + k * x][0] = d + k;
//                                      pq.push({-dist[v + k * x][0], v + k * x, 0});
//                                }
//                          }
//
//                          for(int k = 1; v - k * x >= 0; k++) {
//                                if(dist[v - k * x][0] > d + k) {
//                                      dist[v - k * x][0] = d + k;
//                                      pq.push({-dist[v - k * x][0], v - k * x, 0});
//                                }
//                          }
//                    }
              }
              bio[v] = 1;
        }

        if(v + p < N && dist[v + p][p] > d + 1) {
              dist[v + p][p] = d + 1;
              pq.push({-dist[v + p][p], v + p, p});
        }

        if(v - p >= 0 && dist[v - p][p] > d + 1) {
              dist[v - p][p] = d + 1;
              pq.push({-dist[v - p][p], v - p, p});
        }
    }

    int ans = inf;
    //for(int k = 0; k < B; k++)
    for(int k = 0; k < N; k++)
        ans = min(ans, dist[f][k]);

    if(ans == inf)
        ans = -1;

    cout << ans << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	16340 KB	Output is correct
2	Correct	7 ms	16212 KB	Output is correct
3	Correct	9 ms	16468 KB	Output is correct
4	Correct	7 ms	16320 KB	Output is correct
5	Correct	7 ms	16212 KB	Output is correct
6	Correct	7 ms	16340 KB	Output is correct
7	Correct	7 ms	16212 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	16300 KB	Output is correct
2	Correct	7 ms	16212 KB	Output is correct
3	Correct	8 ms	16288 KB	Output is correct
4	Correct	8 ms	16316 KB	Output is correct
5	Correct	7 ms	16212 KB	Output is correct
6	Correct	7 ms	16260 KB	Output is correct
7	Correct	7 ms	16308 KB	Output is correct
8	Correct	7 ms	16212 KB	Output is correct
9	Correct	8 ms	16212 KB	Output is correct
10	Correct	10 ms	16340 KB	Output is correct
11	Correct	16 ms	16444 KB	Output is correct
12	Correct	7 ms	16340 KB	Output is correct
13	Correct	7 ms	16340 KB	Output is correct
14	Correct	20 ms	16352 KB	Output is correct
15	Correct	19 ms	16340 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	16332 KB	Output is correct
2	Correct	7 ms	16268 KB	Output is correct
3	Correct	7 ms	16264 KB	Output is correct
4	Correct	9 ms	16328 KB	Output is correct
5	Correct	7 ms	16212 KB	Output is correct
6	Correct	7 ms	16212 KB	Output is correct
7	Correct	7 ms	16224 KB	Output is correct
8	Correct	7 ms	16212 KB	Output is correct
9	Correct	8 ms	16340 KB	Output is correct
10	Correct	10 ms	16340 KB	Output is correct
11	Correct	16 ms	16440 KB	Output is correct
12	Correct	10 ms	16340 KB	Output is correct
13	Correct	8 ms	16340 KB	Output is correct
14	Correct	20 ms	16400 KB	Output is correct
15	Correct	20 ms	16340 KB	Output is correct
16	Correct	8 ms	16340 KB	Output is correct
17	Correct	12 ms	16444 KB	Output is correct
18	Correct	7 ms	16336 KB	Output is correct
19	Correct	7 ms	16288 KB	Output is correct
20	Correct	9 ms	16340 KB	Output is correct
21	Correct	8 ms	16340 KB	Output is correct
22	Correct	7 ms	16340 KB	Output is correct
23	Correct	8 ms	16340 KB	Output is correct
24	Correct	9 ms	16376 KB	Output is correct
25	Correct	8 ms	16340 KB	Output is correct
26	Correct	8 ms	16400 KB	Output is correct
27	Correct	8 ms	16336 KB	Output is correct
28	Correct	8 ms	16340 KB	Output is correct
29	Correct	13 ms	16316 KB	Output is correct
30	Correct	9 ms	16340 KB	Output is correct
31	Correct	10 ms	16340 KB	Output is correct
32	Correct	9 ms	16288 KB	Output is correct
33	Correct	22 ms	16340 KB	Output is correct
34	Correct	21 ms	16408 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	16300 KB	Output is correct
2	Correct	7 ms	16212 KB	Output is correct
3	Correct	7 ms	16340 KB	Output is correct
4	Correct	7 ms	16212 KB	Output is correct
5	Correct	7 ms	16212 KB	Output is correct
6	Correct	7 ms	16268 KB	Output is correct
7	Correct	7 ms	16212 KB	Output is correct
8	Correct	7 ms	16212 KB	Output is correct
9	Correct	7 ms	16340 KB	Output is correct
10	Correct	10 ms	16264 KB	Output is correct
11	Correct	16 ms	16316 KB	Output is correct
12	Correct	10 ms	16468 KB	Output is correct
13	Correct	8 ms	16340 KB	Output is correct
14	Correct	20 ms	16404 KB	Output is correct
15	Correct	20 ms	16404 KB	Output is correct
16	Correct	9 ms	16340 KB	Output is correct
17	Correct	12 ms	16340 KB	Output is correct
18	Correct	7 ms	16360 KB	Output is correct
19	Correct	7 ms	16340 KB	Output is correct
20	Correct	8 ms	16340 KB	Output is correct
21	Correct	7 ms	16280 KB	Output is correct
22	Correct	7 ms	16340 KB	Output is correct
23	Correct	8 ms	16340 KB	Output is correct
24	Correct	9 ms	16340 KB	Output is correct
25	Correct	8 ms	16344 KB	Output is correct
26	Correct	8 ms	16340 KB	Output is correct
27	Correct	8 ms	16340 KB	Output is correct
28	Correct	9 ms	16340 KB	Output is correct
29	Correct	13 ms	16340 KB	Output is correct
30	Correct	9 ms	16272 KB	Output is correct
31	Correct	10 ms	16340 KB	Output is correct
32	Correct	12 ms	16300 KB	Output is correct
33	Correct	19 ms	16340 KB	Output is correct
34	Correct	20 ms	16340 KB	Output is correct
35	Correct	48 ms	17068 KB	Output is correct
36	Correct	12 ms	16436 KB	Output is correct
37	Correct	38 ms	16952 KB	Output is correct
38	Correct	40 ms	17088 KB	Output is correct
39	Correct	37 ms	17076 KB	Output is correct
40	Correct	37 ms	17048 KB	Output is correct
41	Correct	51 ms	17048 KB	Output is correct
42	Correct	16 ms	17036 KB	Output is correct
43	Correct	12 ms	17040 KB	Output is correct
44	Correct	11 ms	17092 KB	Output is correct
45	Correct	78 ms	17036 KB	Output is correct
46	Correct	78 ms	17044 KB	Output is correct

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	16304 KB	Output is correct
2	Correct	6 ms	16284 KB	Output is correct
3	Correct	9 ms	16236 KB	Output is correct
4	Correct	6 ms	16276 KB	Output is correct
5	Correct	6 ms	16220 KB	Output is correct
6	Correct	8 ms	16360 KB	Output is correct
7	Correct	6 ms	16212 KB	Output is correct
8	Correct	6 ms	16300 KB	Output is correct
9	Correct	8 ms	16288 KB	Output is correct
10	Correct	9 ms	16340 KB	Output is correct
11	Correct	16 ms	16340 KB	Output is correct
12	Correct	8 ms	16340 KB	Output is correct
13	Correct	8 ms	16340 KB	Output is correct
14	Correct	19 ms	16372 KB	Output is correct
15	Correct	19 ms	16404 KB	Output is correct
16	Correct	7 ms	16340 KB	Output is correct
17	Correct	12 ms	16440 KB	Output is correct
18	Correct	8 ms	16340 KB	Output is correct
19	Correct	7 ms	16284 KB	Output is correct
20	Correct	10 ms	16340 KB	Output is correct
21	Correct	7 ms	16340 KB	Output is correct
22	Correct	6 ms	16340 KB	Output is correct
23	Correct	8 ms	16340 KB	Output is correct
24	Correct	8 ms	16340 KB	Output is correct
25	Correct	8 ms	16340 KB	Output is correct
26	Correct	8 ms	16320 KB	Output is correct
27	Correct	9 ms	16356 KB	Output is correct
28	Correct	8 ms	16340 KB	Output is correct
29	Correct	12 ms	16340 KB	Output is correct
30	Correct	8 ms	16340 KB	Output is correct
31	Correct	10 ms	16340 KB	Output is correct
32	Correct	10 ms	16320 KB	Output is correct
33	Correct	20 ms	16340 KB	Output is correct
34	Correct	20 ms	16340 KB	Output is correct
35	Correct	44 ms	17064 KB	Output is correct
36	Correct	17 ms	16468 KB	Output is correct
37	Correct	44 ms	17036 KB	Output is correct
38	Correct	51 ms	17016 KB	Output is correct
39	Correct	40 ms	17024 KB	Output is correct
40	Correct	38 ms	17100 KB	Output is correct
41	Correct	38 ms	17012 KB	Output is correct
42	Correct	12 ms	17040 KB	Output is correct
43	Correct	12 ms	17040 KB	Output is correct
44	Correct	13 ms	17068 KB	Output is correct
45	Correct	81 ms	17044 KB	Output is correct
46	Correct	87 ms	17028 KB	Output is correct
47	Runtime error	24 ms	32852 KB	Execution killed with signal 11
48	Halted	0 ms	0 KB	-

답안 #766357

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