oj.uz

답안 #709877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709877 2023-03-14T18:30:55 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 497 ms 262144 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

const int INF = 1e9;
const int B = 80;
const int MAXN = 3e4 + 5;

vector<pair<int, int> > d;

int dist[MAXN][B];
vector<array<int, 3> > g[MAXN][B];

int main()
{
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    d.resize(m);
    vector<int> big;
    for (int i = 0; i < m; i++)
    {
        cin >> d[i].first >> d[i].second;
        if (d[i].second >= B)
        {
            big.push_back(i);
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < B; j++)
            dist[i][j] = INF;
    for (int i = 0; i < m; i++)
    {
        if (d[i].second >= B) continue;
        g[d[i].first][0].push_back({d[i].first, d[i].second, 0});
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j < B; j++)
        {
            if (i - j >= 0)
            {
                g[i][j].push_back({i - j, 0, 1});
                g[i][j].push_back({i - j, j, 1});
            }
            if (i + j < n)
            {
                g[i][j].push_back({i + j, 0, 1});
                g[i][j].push_back({i + j, j, 1});
            }
        }
    }
    for (auto& i : big)
    {
        for (int j = d[i].first, k = 0; j < n; j += d[i].second, k++)
        {
            g[d[i].first][0].push_back({j, 0, k});
        }
        for (int j = d[i].first, k = 0; j >= 0; j -= d[i].second,  k++)
        {
            g[d[i].first][0].push_back({j, 0, k});
        }
    }
    set<array<int, 3> > st;
    st.insert({0, d[0].first, 0});
    dist[d[0].first][0] = 0;
    while (!st.empty())
    {
        auto [dst, pos, pw] = *st.begin();
        st.erase(st.begin());
        if (dst > dist[pos][pw]) continue;
        for (auto& [psu, pwu, w] : g[pos][pw])
        {
            if (dist[psu][pwu] > dst + w)
            {
                st.erase({dist[psu][pwu], psu, pwu});
                dist[psu][pwu] = dst + w;
                st.insert({dist[psu][pwu], psu, pwu});
            }
        }
    }
    int mn = INF;
    for (int i = 0; i < B; i++)
        mn = min(mn, dist[d[1].first][i]);
    if (mn == INF)
        cout << -1;
    else
        cout << mn;
    return 0;
}
/*
small
(i, j) -1> (i - j, 0), (i + j, 0)
(i, 0) -0> (i, j)
(i, j) -1> (i - j, j), (i + j, j)
large
(i, 0) -1> (i + j, 0)
(i, 0) -1> (i - j, 0)
*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 56660 KB Output is correct
2 Correct 28 ms 56696 KB Output is correct
3 Correct 27 ms 56668 KB Output is correct
4 Correct 27 ms 56656 KB Output is correct
5 Correct 27 ms 56692 KB Output is correct
6 Correct 27 ms 56696 KB Output is correct
7 Correct 28 ms 56648 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 56660 KB Output is correct
2 Correct 28 ms 56684 KB Output is correct
3 Correct 27 ms 56644 KB Output is correct
4 Correct 30 ms 56692 KB Output is correct
5 Correct 27 ms 56648 KB Output is correct
6 Correct 27 ms 56668 KB Output is correct
7 Correct 26 ms 56660 KB Output is correct
8 Correct 26 ms 56660 KB Output is correct
9 Correct 28 ms 56784 KB Output is correct
10 Correct 28 ms 56988 KB Output is correct
11 Correct 31 ms 57096 KB Output is correct
12 Correct 28 ms 56972 KB Output is correct
13 Correct 28 ms 57076 KB Output is correct
14 Correct 29 ms 57192 KB Output is correct
15 Correct 30 ms 57144 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 56664 KB Output is correct
2 Correct 27 ms 56676 KB Output is correct
3 Correct 27 ms 56648 KB Output is correct
4 Correct 30 ms 56640 KB Output is correct
5 Correct 28 ms 56616 KB Output is correct
6 Correct 28 ms 56672 KB Output is correct
7 Correct 27 ms 56660 KB Output is correct
8 Correct 27 ms 56748 KB Output is correct
9 Correct 27 ms 56824 KB Output is correct
10 Correct 30 ms 57028 KB Output is correct
11 Correct 33 ms 57080 KB Output is correct
12 Correct 29 ms 56952 KB Output is correct
13 Correct 29 ms 57044 KB Output is correct
14 Correct 29 ms 57096 KB Output is correct
15 Correct 29 ms 57168 KB Output is correct
16 Correct 28 ms 57552 KB Output is correct
17 Correct 36 ms 60496 KB Output is correct
18 Correct 47 ms 65704 KB Output is correct
19 Correct 46 ms 67032 KB Output is correct
20 Correct 45 ms 67072 KB Output is correct
21 Correct 31 ms 58604 KB Output is correct
22 Correct 44 ms 65860 KB Output is correct
23 Correct 43 ms 65100 KB Output is correct
24 Correct 47 ms 66636 KB Output is correct
25 Correct 46 ms 67072 KB Output is correct
26 Correct 46 ms 67044 KB Output is correct
27 Correct 47 ms 67020 KB Output is correct
28 Correct 47 ms 67172 KB Output is correct
29 Correct 61 ms 67104 KB Output is correct
30 Correct 49 ms 66900 KB Output is correct
31 Correct 52 ms 67004 KB Output is correct
32 Correct 48 ms 67020 KB Output is correct
33 Correct 76 ms 67168 KB Output is correct
34 Correct 76 ms 67184 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 56660 KB Output is correct
2 Correct 26 ms 56588 KB Output is correct
3 Correct 28 ms 56672 KB Output is correct
4 Correct 27 ms 56692 KB Output is correct
5 Correct 26 ms 56624 KB Output is correct
6 Correct 27 ms 56596 KB Output is correct
7 Correct 27 ms 56656 KB Output is correct
8 Correct 28 ms 56688 KB Output is correct
9 Correct 28 ms 56716 KB Output is correct
10 Correct 29 ms 57012 KB Output is correct
11 Correct 30 ms 57128 KB Output is correct
12 Correct 29 ms 57044 KB Output is correct
13 Correct 28 ms 56944 KB Output is correct
14 Correct 30 ms 57148 KB Output is correct
15 Correct 30 ms 57252 KB Output is correct
16 Correct 29 ms 57572 KB Output is correct
17 Correct 36 ms 60572 KB Output is correct
18 Correct 43 ms 65636 KB Output is correct
19 Correct 45 ms 67148 KB Output is correct
20 Correct 44 ms 67084 KB Output is correct
21 Correct 30 ms 58524 KB Output is correct
22 Correct 42 ms 65852 KB Output is correct
23 Correct 43 ms 64960 KB Output is correct
24 Correct 49 ms 66652 KB Output is correct
25 Correct 47 ms 67136 KB Output is correct
26 Correct 49 ms 67020 KB Output is correct
27 Correct 48 ms 67040 KB Output is correct
28 Correct 49 ms 67152 KB Output is correct
29 Correct 61 ms 67068 KB Output is correct
30 Correct 50 ms 67016 KB Output is correct
31 Correct 54 ms 66936 KB Output is correct
32 Correct 51 ms 67040 KB Output is correct
33 Correct 75 ms 67124 KB Output is correct
34 Correct 73 ms 67180 KB Output is correct
35 Correct 68 ms 66108 KB Output is correct
36 Correct 40 ms 62540 KB Output is correct
37 Correct 82 ms 69240 KB Output is correct
38 Correct 83 ms 69744 KB Output is correct
39 Correct 77 ms 69796 KB Output is correct
40 Correct 77 ms 69844 KB Output is correct
41 Correct 83 ms 69904 KB Output is correct
42 Correct 49 ms 67536 KB Output is correct
43 Correct 51 ms 67564 KB Output is correct
44 Correct 51 ms 67600 KB Output is correct
45 Correct 96 ms 73660 KB Output is correct
46 Correct 99 ms 73824 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 56660 KB Output is correct
2 Correct 28 ms 56648 KB Output is correct
3 Correct 27 ms 56636 KB Output is correct
4 Correct 28 ms 56628 KB Output is correct
5 Correct 28 ms 56656 KB Output is correct
6 Correct 28 ms 56660 KB Output is correct
7 Correct 28 ms 56632 KB Output is correct
8 Correct 29 ms 56708 KB Output is correct
9 Correct 28 ms 56720 KB Output is correct
10 Correct 29 ms 57044 KB Output is correct
11 Correct 29 ms 57044 KB Output is correct
12 Correct 29 ms 57044 KB Output is correct
13 Correct 29 ms 56984 KB Output is correct
14 Correct 29 ms 57100 KB Output is correct
15 Correct 29 ms 57080 KB Output is correct
16 Correct 29 ms 57476 KB Output is correct
17 Correct 41 ms 60640 KB Output is correct
18 Correct 46 ms 65624 KB Output is correct
19 Correct 47 ms 67020 KB Output is correct
20 Correct 45 ms 67060 KB Output is correct
21 Correct 32 ms 58524 KB Output is correct
22 Correct 44 ms 65820 KB Output is correct
23 Correct 43 ms 64996 KB Output is correct
24 Correct 48 ms 66584 KB Output is correct
25 Correct 48 ms 67068 KB Output is correct
26 Correct 47 ms 66972 KB Output is correct
27 Correct 47 ms 67052 KB Output is correct
28 Correct 48 ms 67132 KB Output is correct
29 Correct 65 ms 66976 KB Output is correct
30 Correct 49 ms 66892 KB Output is correct
31 Correct 60 ms 67052 KB Output is correct
32 Correct 55 ms 66936 KB Output is correct
33 Correct 77 ms 67148 KB Output is correct
34 Correct 74 ms 67112 KB Output is correct
35 Correct 61 ms 66116 KB Output is correct
36 Correct 41 ms 62476 KB Output is correct
37 Correct 81 ms 69192 KB Output is correct
38 Correct 78 ms 69792 KB Output is correct
39 Correct 81 ms 69796 KB Output is correct
40 Correct 78 ms 69768 KB Output is correct
41 Correct 78 ms 69792 KB Output is correct
42 Correct 50 ms 67528 KB Output is correct
43 Correct 50 ms 67592 KB Output is correct
44 Correct 51 ms 67572 KB Output is correct
45 Correct 102 ms 73648 KB Output is correct
46 Correct 99 ms 73780 KB Output is correct
47 Correct 331 ms 130088 KB Output is correct
48 Correct 256 ms 181468 KB Output is correct
49 Correct 259 ms 192484 KB Output is correct
50 Correct 308 ms 205372 KB Output is correct
51 Correct 388 ms 219204 KB Output is correct
52 Correct 463 ms 219356 KB Output is correct
53 Correct 347 ms 215696 KB Output is correct
54 Correct 313 ms 214368 KB Output is correct
55 Correct 297 ms 214264 KB Output is correct
56 Correct 304 ms 215344 KB Output is correct
57 Correct 497 ms 214476 KB Output is correct
58 Correct 309 ms 214856 KB Output is correct
59 Correct 319 ms 214856 KB Output is correct
60 Correct 362 ms 215800 KB Output is correct
61 Correct 355 ms 215252 KB Output is correct
62 Correct 392 ms 219624 KB Output is correct
63 Correct 429 ms 249948 KB Output is correct
64 Runtime error 306 ms 262144 KB Execution killed with signal 9
65 Halted 0 ms 0 KB -