답안 #957493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
957493	2024-04-03T21:41:37 Z	aykhn	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	23 ms	1384 KB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F

const int MXN = 3e4 + 5;

int b[MXN], p[MXN], dist[MXN];
vector<int> adj[MXN];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) dist[i] = inf;
    for (int i = 0; i < m; i++)
    {
        cin >> b[i] >> p[i];
        adj[--b[i]].push_back(p[i]);
    }
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    dist[b[0]] = 0;
    pq.push({0, b[0]});
    while (!pq.empty())
    {
        array<int, 2> f = pq.top();
        pq.pop();
        if (f[0] > dist[f[1]]) continue;
        for (int v : adj[f[1]])
        {
            for (int i = f[1] - v; i >= 0; i -= v)
            {
                if (dist[i] > dist[f[1]] + (f[1] - i) / v)
                {
                    dist[i] = dist[f[1]] + (f[1] - i) / v;
                    pq.push({dist[i], i});
                }
            }
            for (int i = f[1] + v; i < n; i += v)
            {
                if (dist[i] > dist[f[1]] + (i - f[1]) / v)
                {
                    dist[i] = dist[f[1]] + (i - f[1]) / v;
                    pq.push({dist[i], i});
                }
            }
        }
    }
    cout << (dist[b[1]] >= inf ? -1 : dist[b[1]]) << '\n';
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1116 KB	Output is correct
2	Correct	1 ms	1116 KB	Output is correct
3	Correct	1 ms	1116 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	1 ms	1116 KB	Output is correct
6	Correct	1 ms	1116 KB	Output is correct
7	Correct	1 ms	1360 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1116 KB	Output is correct
2	Correct	1 ms	1116 KB	Output is correct
3	Correct	1 ms	1116 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	1 ms	1116 KB	Output is correct
6	Correct	1 ms	1112 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1368 KB	Output is correct
9	Correct	1 ms	1116 KB	Output is correct
10	Correct	1 ms	1116 KB	Output is correct
11	Correct	1 ms	1116 KB	Output is correct
12	Correct	2 ms	1168 KB	Output is correct
13	Correct	2 ms	1176 KB	Output is correct
14	Correct	1 ms	1116 KB	Output is correct
15	Correct	1 ms	1116 KB	Output is correct

Subtask #3

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1116 KB	Output is correct
2	Correct	1 ms	1116 KB	Output is correct
3	Correct	1 ms	1116 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	1 ms	1116 KB	Output is correct
6	Correct	1 ms	1116 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	1 ms	1116 KB	Output is correct
10	Correct	1 ms	1116 KB	Output is correct
11	Correct	1 ms	1116 KB	Output is correct
12	Correct	2 ms	1112 KB	Output is correct
13	Correct	2 ms	1116 KB	Output is correct
14	Correct	1 ms	1116 KB	Output is correct
15	Correct	1 ms	1116 KB	Output is correct
16	Correct	1 ms	1112 KB	Output is correct
17	Correct	1 ms	1112 KB	Output is correct
18	Correct	1 ms	1116 KB	Output is correct
19	Correct	1 ms	1116 KB	Output is correct
20	Correct	23 ms	1116 KB	Output is correct
21	Correct	1 ms	1116 KB	Output is correct
22	Correct	1 ms	1116 KB	Output is correct
23	Correct	1 ms	1176 KB	Output is correct
24	Correct	2 ms	1116 KB	Output is correct
25	Correct	1 ms	1372 KB	Output is correct
26	Correct	21 ms	1112 KB	Output is correct
27	Correct	20 ms	1116 KB	Output is correct
28	Incorrect	1 ms	1112 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #4

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1116 KB	Output is correct
2	Correct	1 ms	1116 KB	Output is correct
3	Correct	1 ms	1132 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	1 ms	1164 KB	Output is correct
6	Correct	1 ms	1116 KB	Output is correct
7	Correct	1 ms	1124 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	1 ms	1116 KB	Output is correct
10	Correct	1 ms	1116 KB	Output is correct
11	Correct	1 ms	1116 KB	Output is correct
12	Correct	2 ms	1116 KB	Output is correct
13	Correct	2 ms	1248 KB	Output is correct
14	Correct	1 ms	1116 KB	Output is correct
15	Correct	1 ms	1116 KB	Output is correct
16	Correct	1 ms	1112 KB	Output is correct
17	Correct	1 ms	1116 KB	Output is correct
18	Correct	1 ms	1116 KB	Output is correct
19	Correct	1 ms	1116 KB	Output is correct
20	Correct	23 ms	1368 KB	Output is correct
21	Correct	1 ms	1116 KB	Output is correct
22	Correct	1 ms	1116 KB	Output is correct
23	Correct	1 ms	1116 KB	Output is correct
24	Correct	2 ms	1116 KB	Output is correct
25	Correct	1 ms	1372 KB	Output is correct
26	Correct	21 ms	1288 KB	Output is correct
27	Correct	20 ms	1116 KB	Output is correct
28	Incorrect	1 ms	1112 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1116 KB	Output is correct
2	Correct	1 ms	1116 KB	Output is correct
3	Correct	1 ms	1116 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	1 ms	1116 KB	Output is correct
6	Correct	1 ms	1116 KB	Output is correct
7	Correct	1 ms	1112 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	1 ms	1116 KB	Output is correct
10	Correct	1 ms	1112 KB	Output is correct
11	Correct	1 ms	1116 KB	Output is correct
12	Correct	2 ms	1116 KB	Output is correct
13	Correct	2 ms	1116 KB	Output is correct
14	Correct	1 ms	1116 KB	Output is correct
15	Correct	1 ms	1176 KB	Output is correct
16	Correct	1 ms	1116 KB	Output is correct
17	Correct	1 ms	1368 KB	Output is correct
18	Correct	1 ms	1116 KB	Output is correct
19	Correct	1 ms	1116 KB	Output is correct
20	Correct	23 ms	1372 KB	Output is correct
21	Correct	1 ms	1116 KB	Output is correct
22	Correct	1 ms	1116 KB	Output is correct
23	Correct	1 ms	1116 KB	Output is correct
24	Correct	1 ms	1116 KB	Output is correct
25	Correct	1 ms	1384 KB	Output is correct
26	Correct	22 ms	1116 KB	Output is correct
27	Correct	20 ms	1116 KB	Output is correct
28	Incorrect	2 ms	1116 KB	Output isn't correct
29	Halted	0 ms	0 KB	-