Submission #477290

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
477290	2021-10-01T15:16:10 Z	KienTran	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	23 ms	396 KB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int O = 3e4 + 5;
const int inf = 1e9;

int n, m, b[O], d[O], p[O];
bool inq[O];

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i){
        cin >> b[i] >> p[i];
    }

    for (int i = 1; i <= m; ++ i) d[i] = inf;

    d[1] = 0;
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
    q.push(make_pair(0, 1)); inq[1] = true;

    while (q.size()){
        int u = q.top().second;
        int du = q.top().first;

        q.pop();
        if (du != d[u]) continue;

        inq[u] = false;
        for (int v = 1; v <= m; ++ v){
            if (v != u && d[v] > d[u] + abs(b[u] - b[v]) / p[u] && abs(b[u] - b[v]) % p[u] == 0){
                d[v] = d[u] + abs(b[u] - b[v]) / p[u];
                if (inq[v] == 0){
                    q.push(make_pair(d[v], v));
                    inq[v] = true;
                }
            }
        }
    }

    if (d[2] >= inf) cout << -1;
    else cout << d[2];
}

Compilation message

skyscraper.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main(){
      | ^~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct

Subtask #2

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	14 ms	388 KB	Output is correct
12	Correct	22 ms	392 KB	Output is correct
13	Correct	22 ms	332 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Incorrect	2 ms	332 KB	Output isn't correct

Subtask #3

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	14 ms	384 KB	Output is correct
12	Correct	22 ms	368 KB	Output is correct
13	Correct	23 ms	388 KB	Output is correct
14	Correct	3 ms	332 KB	Output is correct
15	Incorrect	2 ms	332 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	14 ms	332 KB	Output is correct
12	Correct	23 ms	388 KB	Output is correct
13	Correct	23 ms	396 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Incorrect	2 ms	332 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	14 ms	332 KB	Output is correct
12	Correct	22 ms	384 KB	Output is correct
13	Correct	23 ms	332 KB	Output is correct
14	Correct	3 ms	332 KB	Output is correct
15	Incorrect	2 ms	332 KB	Output isn't correct
16	Halted	0 ms	0 KB	-