답안 #960684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960684	2024-04-10T22:46:20 Z	3omar_ahmed	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	239 ms	262144 KB

skyscraper

#include <bits/stdc++.h>
using namespace std ;
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 2004 * 2004;
vector < int > dis(N, 1e9);
vector < vector < pair < int , int >>> adj(N);
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    int n, m;
    cin >> n >> m;
    pair < int , int > first, second;
    vector < vector < int >> arr(1 + n);
    for(int i = 0 ; i < m ; i++) {
        int a, b;
        cin >> a >> b;
        if(i == 0) {
            first = {a, b};
        } else if(i == 1) {
            second = {a, b};
        }
        arr[a].push_back(b);
    }
    for(int i = 0 ; i < n ; i++) {
        for(auto j : arr[i]) {
            int node = (i * (n + 1) + j);
            adj[i * (n + 1) + n + 1].push_back({node, 0});
            adj[node].push_back({i * (n + 1) + n + 1, 0});
            for(int k = 1 ; k <= n ; k++) {
                if(i + j * k < n) {
                    adj[node].push_back({(i + j * k) * (n + 1) + n + 1, k});
                }
                if(i - j * k >= 0) {
                    adj[node].push_back({(i - j * k) * (n + 1) + n + 1, k});
                }
            }
        }
    }
    int st = first.first * (n + 1) + first.second;
    priority_queue < pair < int , int >> pq;
    pq.push({0, st});
    dis[st] = 0; 
    while(pq.size()) {
        auto top = pq.top();
        pq.pop();
        top.first *= -1;
        if(top.first != dis[top.second])
            continue;
        for(auto ch : adj[top.second]) {
            if(dis[ch.first] > top.first + ch.second) {
                dis[ch.first] = top.first + ch.second;
                pq.push({-dis[ch.first], ch.first});
            }
        }
    }
    int ed = second.first * (n + 1) + second.second;
    if(dis[ed] >= 1e8) dis[ed] = -1;
    cout << dis[ed] << endl;
    return 0 ;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	110476 KB	Output is correct
2	Correct	26 ms	110492 KB	Output is correct
3	Correct	28 ms	110468 KB	Output is correct
4	Correct	27 ms	110428 KB	Output is correct
5	Correct	27 ms	110428 KB	Output is correct
6	Correct	27 ms	110428 KB	Output is correct
7	Correct	28 ms	110464 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	110580 KB	Output is correct
2	Correct	28 ms	110580 KB	Output is correct
3	Correct	26 ms	110424 KB	Output is correct
4	Correct	27 ms	110428 KB	Output is correct
5	Correct	27 ms	110224 KB	Output is correct
6	Correct	26 ms	110428 KB	Output is correct
7	Correct	26 ms	110424 KB	Output is correct
8	Correct	27 ms	110424 KB	Output is correct
9	Correct	26 ms	110332 KB	Output is correct
10	Correct	26 ms	110428 KB	Output is correct
11	Correct	27 ms	110640 KB	Output is correct
12	Correct	44 ms	112592 KB	Output is correct
13	Correct	29 ms	112596 KB	Output is correct
14	Correct	28 ms	110428 KB	Output is correct
15	Correct	27 ms	110520 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	110428 KB	Output is correct
2	Correct	26 ms	110256 KB	Output is correct
3	Correct	26 ms	110428 KB	Output is correct
4	Correct	28 ms	110428 KB	Output is correct
5	Correct	28 ms	110428 KB	Output is correct
6	Correct	26 ms	110424 KB	Output is correct
7	Correct	26 ms	110424 KB	Output is correct
8	Correct	26 ms	110428 KB	Output is correct
9	Correct	26 ms	110428 KB	Output is correct
10	Correct	27 ms	110428 KB	Output is correct
11	Correct	27 ms	110428 KB	Output is correct
12	Correct	32 ms	112600 KB	Output is correct
13	Correct	28 ms	112600 KB	Output is correct
14	Correct	27 ms	110428 KB	Output is correct
15	Correct	27 ms	110420 KB	Output is correct
16	Correct	26 ms	110428 KB	Output is correct
17	Correct	29 ms	110684 KB	Output is correct
18	Correct	28 ms	110660 KB	Output is correct
19	Correct	26 ms	110428 KB	Output is correct
20	Correct	89 ms	142676 KB	Output is correct
21	Correct	27 ms	110476 KB	Output is correct
22	Correct	27 ms	110656 KB	Output is correct
23	Correct	28 ms	110700 KB	Output is correct
24	Correct	30 ms	110676 KB	Output is correct
25	Correct	32 ms	110680 KB	Output is correct
26	Correct	80 ms	144560 KB	Output is correct
27	Correct	68 ms	144412 KB	Output is correct
28	Correct	31 ms	110936 KB	Output is correct
29	Correct	29 ms	111192 KB	Output is correct
30	Correct	27 ms	110676 KB	Output is correct
31	Correct	29 ms	111012 KB	Output is correct
32	Correct	29 ms	110724 KB	Output is correct
33	Correct	34 ms	111964 KB	Output is correct
34	Correct	33 ms	112212 KB	Output is correct

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	110428 KB	Output is correct
2	Correct	25 ms	110392 KB	Output is correct
3	Correct	26 ms	110428 KB	Output is correct
4	Correct	28 ms	110412 KB	Output is correct
5	Correct	26 ms	110416 KB	Output is correct
6	Correct	26 ms	110500 KB	Output is correct
7	Correct	25 ms	110424 KB	Output is correct
8	Correct	26 ms	110424 KB	Output is correct
9	Correct	26 ms	110276 KB	Output is correct
10	Correct	26 ms	110500 KB	Output is correct
11	Correct	27 ms	110424 KB	Output is correct
12	Correct	30 ms	112600 KB	Output is correct
13	Correct	29 ms	112596 KB	Output is correct
14	Correct	27 ms	110604 KB	Output is correct
15	Correct	29 ms	110548 KB	Output is correct
16	Correct	29 ms	110428 KB	Output is correct
17	Correct	29 ms	110680 KB	Output is correct
18	Correct	27 ms	110612 KB	Output is correct
19	Correct	27 ms	110428 KB	Output is correct
20	Correct	79 ms	142672 KB	Output is correct
21	Correct	26 ms	110560 KB	Output is correct
22	Correct	27 ms	110428 KB	Output is correct
23	Correct	31 ms	110856 KB	Output is correct
24	Correct	30 ms	110676 KB	Output is correct
25	Correct	32 ms	110676 KB	Output is correct
26	Correct	68 ms	144312 KB	Output is correct
27	Correct	67 ms	144308 KB	Output is correct
28	Correct	31 ms	110940 KB	Output is correct
29	Correct	33 ms	111124 KB	Output is correct
30	Correct	29 ms	110744 KB	Output is correct
31	Correct	28 ms	110932 KB	Output is correct
32	Correct	29 ms	110920 KB	Output is correct
33	Correct	33 ms	111952 KB	Output is correct
34	Correct	33 ms	112100 KB	Output is correct
35	Correct	75 ms	113236 KB	Output is correct
36	Correct	33 ms	110940 KB	Output is correct
37	Correct	79 ms	114336 KB	Output is correct
38	Correct	113 ms	114208 KB	Output is correct
39	Correct	104 ms	114512 KB	Output is correct
40	Correct	104 ms	114292 KB	Output is correct
41	Correct	108 ms	114204 KB	Output is correct
42	Runtime error	239 ms	262144 KB	Execution killed with signal 9
43	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	110424 KB	Output is correct
2	Correct	28 ms	110320 KB	Output is correct
3	Correct	31 ms	110492 KB	Output is correct
4	Correct	26 ms	110680 KB	Output is correct
5	Correct	27 ms	110424 KB	Output is correct
6	Correct	26 ms	110424 KB	Output is correct
7	Correct	26 ms	110668 KB	Output is correct
8	Correct	28 ms	110424 KB	Output is correct
9	Correct	27 ms	110428 KB	Output is correct
10	Correct	27 ms	110428 KB	Output is correct
11	Correct	26 ms	110416 KB	Output is correct
12	Correct	30 ms	112488 KB	Output is correct
13	Correct	30 ms	112600 KB	Output is correct
14	Correct	31 ms	110612 KB	Output is correct
15	Correct	31 ms	110452 KB	Output is correct
16	Correct	31 ms	110424 KB	Output is correct
17	Correct	29 ms	110680 KB	Output is correct
18	Correct	27 ms	110672 KB	Output is correct
19	Correct	27 ms	110428 KB	Output is correct
20	Correct	78 ms	142620 KB	Output is correct
21	Correct	30 ms	110440 KB	Output is correct
22	Correct	27 ms	110500 KB	Output is correct
23	Correct	33 ms	110428 KB	Output is correct
24	Correct	33 ms	110828 KB	Output is correct
25	Correct	32 ms	110680 KB	Output is correct
26	Correct	69 ms	145592 KB	Output is correct
27	Correct	68 ms	143800 KB	Output is correct
28	Correct	34 ms	110940 KB	Output is correct
29	Correct	30 ms	111196 KB	Output is correct
30	Correct	28 ms	110696 KB	Output is correct
31	Correct	34 ms	110940 KB	Output is correct
32	Correct	28 ms	110852 KB	Output is correct
33	Correct	33 ms	111952 KB	Output is correct
34	Correct	33 ms	111956 KB	Output is correct
35	Correct	81 ms	113288 KB	Output is correct
36	Correct	35 ms	110932 KB	Output is correct
37	Correct	87 ms	114352 KB	Output is correct
38	Correct	107 ms	114344 KB	Output is correct
39	Correct	103 ms	114516 KB	Output is correct
40	Correct	104 ms	114328 KB	Output is correct
41	Correct	104 ms	114272 KB	Output is correct
42	Runtime error	208 ms	262144 KB	Execution killed with signal 9
43	Halted	0 ms	0 KB	-

답안 #960684

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