Submission #960685

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
960685	2024-04-10T22:50:03 Z	3omar_ahmed	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	128 ms	228136 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);
    set < pair < int , int >> s;
    for(int i = 0 ; i < m ; i++) {
        int a, b;
        cin >> a >> b;
        s.insert({a, b});
        if(i == 0) {
            first = {a, b};
        } else if(i == 1) {
            second = {a, b};
        }
        // arr[a].push_back(b);
    }
    for(auto i : s) {
        arr[i.first].push_back(i.second);
    }
    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

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	110420 KB	Output is correct
2	Correct	27 ms	110428 KB	Output is correct
3	Correct	26 ms	110500 KB	Output is correct
4	Correct	27 ms	110468 KB	Output is correct
5	Correct	26 ms	110424 KB	Output is correct
6	Correct	25 ms	110428 KB	Output is correct
7	Correct	27 ms	110428 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	110488 KB	Output is correct
2	Correct	29 ms	110428 KB	Output is correct
3	Correct	27 ms	110332 KB	Output is correct
4	Correct	26 ms	110424 KB	Output is correct
5	Correct	26 ms	110428 KB	Output is correct
6	Correct	25 ms	110480 KB	Output is correct
7	Correct	26 ms	110232 KB	Output is correct
8	Correct	26 ms	110428 KB	Output is correct
9	Correct	26 ms	110428 KB	Output is correct
10	Correct	26 ms	110296 KB	Output is correct
11	Correct	30 ms	110684 KB	Output is correct
12	Correct	29 ms	110476 KB	Output is correct
13	Correct	27 ms	110428 KB	Output is correct
14	Correct	27 ms	110488 KB	Output is correct
15	Correct	29 ms	110680 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	110340 KB	Output is correct
2	Correct	25 ms	110428 KB	Output is correct
3	Correct	25 ms	110492 KB	Output is correct
4	Correct	26 ms	110244 KB	Output is correct
5	Correct	25 ms	110428 KB	Output is correct
6	Correct	26 ms	110428 KB	Output is correct
7	Correct	26 ms	110424 KB	Output is correct
8	Correct	26 ms	110256 KB	Output is correct
9	Correct	29 ms	110264 KB	Output is correct
10	Correct	30 ms	110428 KB	Output is correct
11	Correct	27 ms	110684 KB	Output is correct
12	Correct	26 ms	110428 KB	Output is correct
13	Correct	27 ms	110428 KB	Output is correct
14	Correct	28 ms	110680 KB	Output is correct
15	Correct	28 ms	110680 KB	Output is correct
16	Correct	28 ms	110428 KB	Output is correct
17	Correct	30 ms	110940 KB	Output is correct
18	Correct	30 ms	110676 KB	Output is correct
19	Correct	27 ms	110428 KB	Output is correct
20	Correct	79 ms	142744 KB	Output is correct
21	Correct	27 ms	110428 KB	Output is correct
22	Correct	28 ms	110640 KB	Output is correct
23	Correct	29 ms	110640 KB	Output is correct
24	Correct	32 ms	110684 KB	Output is correct
25	Correct	31 ms	110704 KB	Output is correct
26	Correct	27 ms	110696 KB	Output is correct
27	Correct	28 ms	110540 KB	Output is correct
28	Correct	36 ms	111268 KB	Output is correct
29	Correct	29 ms	111196 KB	Output is correct
30	Correct	28 ms	110684 KB	Output is correct
31	Correct	29 ms	110940 KB	Output is correct
32	Correct	28 ms	110940 KB	Output is correct
33	Correct	33 ms	111968 KB	Output is correct
34	Correct	33 ms	111964 KB	Output is correct

Subtask #4
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	110424 KB	Output is correct
2	Correct	29 ms	110684 KB	Output is correct
3	Correct	26 ms	110420 KB	Output is correct
4	Correct	25 ms	110428 KB	Output is correct
5	Correct	28 ms	110428 KB	Output is correct
6	Correct	26 ms	110428 KB	Output is correct
7	Correct	28 ms	110244 KB	Output is correct
8	Correct	26 ms	110428 KB	Output is correct
9	Correct	29 ms	110428 KB	Output is correct
10	Correct	27 ms	110560 KB	Output is correct
11	Correct	28 ms	110516 KB	Output is correct
12	Correct	26 ms	110264 KB	Output is correct
13	Correct	29 ms	110416 KB	Output is correct
14	Correct	28 ms	110552 KB	Output is correct
15	Correct	27 ms	110684 KB	Output is correct
16	Correct	27 ms	110612 KB	Output is correct
17	Correct	29 ms	110684 KB	Output is correct
18	Correct	30 ms	110468 KB	Output is correct
19	Correct	28 ms	110428 KB	Output is correct
20	Correct	85 ms	142676 KB	Output is correct
21	Correct	27 ms	110428 KB	Output is correct
22	Correct	27 ms	110616 KB	Output is correct
23	Correct	28 ms	110684 KB	Output is correct
24	Correct	32 ms	110684 KB	Output is correct
25	Correct	32 ms	110684 KB	Output is correct
26	Correct	26 ms	110684 KB	Output is correct
27	Correct	32 ms	110428 KB	Output is correct
28	Correct	31 ms	110940 KB	Output is correct
29	Correct	30 ms	111388 KB	Output is correct
30	Correct	29 ms	110768 KB	Output is correct
31	Correct	28 ms	110940 KB	Output is correct
32	Correct	27 ms	110940 KB	Output is correct
33	Correct	33 ms	112104 KB	Output is correct
34	Correct	34 ms	112060 KB	Output is correct
35	Correct	82 ms	114252 KB	Output is correct
36	Correct	34 ms	111192 KB	Output is correct
37	Correct	77 ms	115008 KB	Output is correct
38	Correct	113 ms	115372 KB	Output is correct
39	Correct	114 ms	115708 KB	Output is correct
40	Correct	110 ms	115580 KB	Output is correct
41	Correct	112 ms	115280 KB	Output is correct
42	Correct	31 ms	110684 KB	Output is correct
43	Correct	30 ms	110684 KB	Output is correct
44	Correct	83 ms	143000 KB	Output is correct
45	Correct	115 ms	118584 KB	Output is correct
46	Correct	104 ms	118596 KB	Output is correct

Subtask #5
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	110284 KB	Output is correct
2	Correct	26 ms	110320 KB	Output is correct
3	Correct	27 ms	110280 KB	Output is correct
4	Correct	26 ms	110424 KB	Output is correct
5	Correct	27 ms	110400 KB	Output is correct
6	Correct	26 ms	110432 KB	Output is correct
7	Correct	26 ms	110428 KB	Output is correct
8	Correct	26 ms	110428 KB	Output is correct
9	Correct	26 ms	110424 KB	Output is correct
10	Correct	27 ms	110524 KB	Output is correct
11	Correct	27 ms	110684 KB	Output is correct
12	Correct	26 ms	110428 KB	Output is correct
13	Correct	26 ms	110428 KB	Output is correct
14	Correct	28 ms	110684 KB	Output is correct
15	Correct	28 ms	110680 KB	Output is correct
16	Correct	26 ms	110428 KB	Output is correct
17	Correct	30 ms	110688 KB	Output is correct
18	Correct	31 ms	110684 KB	Output is correct
19	Correct	28 ms	110652 KB	Output is correct
20	Correct	79 ms	142880 KB	Output is correct
21	Correct	27 ms	110428 KB	Output is correct
22	Correct	26 ms	110680 KB	Output is correct
23	Correct	28 ms	110680 KB	Output is correct
24	Correct	29 ms	110760 KB	Output is correct
25	Correct	37 ms	110684 KB	Output is correct
26	Correct	30 ms	110424 KB	Output is correct
27	Correct	27 ms	110424 KB	Output is correct
28	Correct	32 ms	110820 KB	Output is correct
29	Correct	29 ms	111196 KB	Output is correct
30	Correct	30 ms	110680 KB	Output is correct
31	Correct	29 ms	110940 KB	Output is correct
32	Correct	31 ms	110940 KB	Output is correct
33	Correct	34 ms	111960 KB	Output is correct
34	Correct	34 ms	112168 KB	Output is correct
35	Correct	83 ms	114276 KB	Output is correct
36	Correct	34 ms	110972 KB	Output is correct
37	Correct	80 ms	115256 KB	Output is correct
38	Correct	110 ms	115536 KB	Output is correct
39	Correct	115 ms	115496 KB	Output is correct
40	Correct	118 ms	115424 KB	Output is correct
41	Correct	117 ms	115452 KB	Output is correct
42	Correct	30 ms	110684 KB	Output is correct
43	Correct	31 ms	110744 KB	Output is correct
44	Correct	86 ms	143044 KB	Output is correct
45	Correct	106 ms	118540 KB	Output is correct
46	Correct	104 ms	118356 KB	Output is correct
47	Runtime error	128 ms	228136 KB	Execution killed with signal 11
48	Halted	0 ms	0 KB	-

Submission #960685

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