oj.uz

답안 #709889

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709889 2023-03-14T18:37:18 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 259360 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 = 130;
const int MAXN = 3e4 + 5;

vector<pair<int, int> > d;

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

signed 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)
*/

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:43:42: warning: narrowing conversion of 'd.std::vector<std::pair<int, int> >::operator[](((std::vector<std::pair<int, int> >::size_type)i)).std::pair<int, int>::first' from 'int' to 'short int' [-Wnarrowing]
   43 |         g[d[i].first][0].push_back({d[i].first, d[i].second, 0});
skyscraper.cpp:43:54: warning: narrowing conversion of 'd.std::vector<std::pair<int, int> >::operator[](((std::vector<std::pair<int, int> >::size_type)i)).std::pair<int, int>::second' from 'int' to 'short int' [-Wnarrowing]
   43 |         g[d[i].first][0].push_back({d[i].first, d[i].second, 0});
skyscraper.cpp:51:38: warning: narrowing conversion of '(i - j)' from 'int' to 'short int' [-Wnarrowing]
   51 |                 g[i][j].push_back({i - j, 0, 1});
      |                                    ~~^~~
skyscraper.cpp:52:38: warning: narrowing conversion of '(i - j)' from 'int' to 'short int' [-Wnarrowing]
   52 |                 g[i][j].push_back({i - j, j, 1});
      |                                    ~~^~~
skyscraper.cpp:52:43: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   52 |                 g[i][j].push_back({i - j, j, 1});
      |                                           ^
skyscraper.cpp:56:38: warning: narrowing conversion of '(i + j)' from 'int' to 'short int' [-Wnarrowing]
   56 |                 g[i][j].push_back({i + j, 0, 1});
      |                                    ~~^~~
skyscraper.cpp:57:38: warning: narrowing conversion of '(i + j)' from 'int' to 'short int' [-Wnarrowing]
   57 |                 g[i][j].push_back({i + j, j, 1});
      |                                    ~~^~~
skyscraper.cpp:57:43: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   57 |                 g[i][j].push_back({i + j, j, 1});
      |                                           ^
skyscraper.cpp:65:41: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   65 |             g[d[i].first][0].push_back({j, 0, k});
      |                                         ^
skyscraper.cpp:65:47: warning: narrowing conversion of 'k' from 'int' to 'short int' [-Wnarrowing]
   65 |             g[d[i].first][0].push_back({j, 0, k});
      |                                               ^
skyscraper.cpp:69:41: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   69 |             g[d[i].first][0].push_back({j, 0, k});
      |                                         ^
skyscraper.cpp:69:47: warning: narrowing conversion of 'k' from 'int' to 'short int' [-Wnarrowing]
   69 |             g[d[i].first][0].push_back({j, 0, k});
      |                                               ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 91840 KB Output is correct
2 Correct 48 ms 91820 KB Output is correct
3 Correct 53 ms 91872 KB Output is correct
4 Correct 45 ms 91860 KB Output is correct
5 Correct 54 ms 91928 KB Output is correct
6 Correct 49 ms 91908 KB Output is correct
7 Correct 53 ms 91916 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 91852 KB Output is correct
2 Correct 56 ms 91812 KB Output is correct
3 Correct 51 ms 91972 KB Output is correct
4 Correct 51 ms 91836 KB Output is correct
5 Correct 52 ms 91832 KB Output is correct
6 Correct 45 ms 91828 KB Output is correct
7 Correct 48 ms 91872 KB Output is correct
8 Correct 49 ms 91932 KB Output is correct
9 Correct 57 ms 91980 KB Output is correct
10 Correct 58 ms 92108 KB Output is correct
11 Correct 63 ms 92220 KB Output is correct
12 Correct 59 ms 92244 KB Output is correct
13 Correct 49 ms 92272 KB Output is correct
14 Correct 63 ms 92364 KB Output is correct
15 Correct 53 ms 92364 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 91820 KB Output is correct
2 Correct 50 ms 91872 KB Output is correct
3 Correct 54 ms 91928 KB Output is correct
4 Correct 55 ms 91924 KB Output is correct
5 Correct 60 ms 91920 KB Output is correct
6 Correct 47 ms 91852 KB Output is correct
7 Correct 52 ms 91928 KB Output is correct
8 Correct 75 ms 91892 KB Output is correct
9 Correct 59 ms 92024 KB Output is correct
10 Correct 62 ms 92232 KB Output is correct
11 Correct 58 ms 92324 KB Output is correct
12 Correct 51 ms 92144 KB Output is correct
13 Correct 57 ms 92196 KB Output is correct
14 Correct 66 ms 92360 KB Output is correct
15 Correct 57 ms 92324 KB Output is correct
16 Correct 51 ms 92796 KB Output is correct
17 Correct 56 ms 95436 KB Output is correct
18 Correct 72 ms 99832 KB Output is correct
19 Correct 92 ms 101004 KB Output is correct
20 Correct 84 ms 101056 KB Output is correct
21 Correct 56 ms 93756 KB Output is correct
22 Correct 80 ms 99948 KB Output is correct
23 Correct 69 ms 99180 KB Output is correct
24 Correct 74 ms 100708 KB Output is correct
25 Correct 86 ms 101096 KB Output is correct
26 Correct 81 ms 101064 KB Output is correct
27 Correct 70 ms 101020 KB Output is correct
28 Correct 86 ms 101028 KB Output is correct
29 Correct 90 ms 101120 KB Output is correct
30 Correct 77 ms 101032 KB Output is correct
31 Correct 79 ms 101060 KB Output is correct
32 Correct 82 ms 101096 KB Output is correct
33 Correct 99 ms 101096 KB Output is correct
34 Correct 105 ms 101068 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 91924 KB Output is correct
2 Correct 45 ms 91848 KB Output is correct
3 Correct 54 ms 91916 KB Output is correct
4 Correct 43 ms 91796 KB Output is correct
5 Correct 43 ms 91924 KB Output is correct
6 Correct 57 ms 91856 KB Output is correct
7 Correct 43 ms 91928 KB Output is correct
8 Correct 43 ms 91924 KB Output is correct
9 Correct 42 ms 91960 KB Output is correct
10 Correct 59 ms 92112 KB Output is correct
11 Correct 51 ms 92308 KB Output is correct
12 Correct 47 ms 92248 KB Output is correct
13 Correct 44 ms 92156 KB Output is correct
14 Correct 53 ms 92360 KB Output is correct
15 Correct 64 ms 92328 KB Output is correct
16 Correct 48 ms 92784 KB Output is correct
17 Correct 57 ms 95332 KB Output is correct
18 Correct 78 ms 99844 KB Output is correct
19 Correct 84 ms 100980 KB Output is correct
20 Correct 77 ms 101112 KB Output is correct
21 Correct 48 ms 93644 KB Output is correct
22 Correct 78 ms 100044 KB Output is correct
23 Correct 77 ms 99228 KB Output is correct
24 Correct 78 ms 100684 KB Output is correct
25 Correct 78 ms 101024 KB Output is correct
26 Correct 81 ms 100952 KB Output is correct
27 Correct 91 ms 101092 KB Output is correct
28 Correct 93 ms 101116 KB Output is correct
29 Correct 122 ms 101024 KB Output is correct
30 Correct 82 ms 101004 KB Output is correct
31 Correct 84 ms 101044 KB Output is correct
32 Correct 113 ms 100992 KB Output is correct
33 Correct 124 ms 101108 KB Output is correct
34 Correct 102 ms 101188 KB Output is correct
35 Correct 101 ms 99788 KB Output is correct
36 Correct 71 ms 97148 KB Output is correct
37 Correct 128 ms 102316 KB Output is correct
38 Correct 195 ms 102836 KB Output is correct
39 Correct 123 ms 102852 KB Output is correct
40 Correct 124 ms 102856 KB Output is correct
41 Correct 143 ms 102920 KB Output is correct
42 Correct 99 ms 101576 KB Output is correct
43 Correct 88 ms 101660 KB Output is correct
44 Correct 82 ms 101684 KB Output is correct
45 Correct 165 ms 104412 KB Output is correct
46 Correct 154 ms 104372 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 91856 KB Output is correct
2 Correct 45 ms 91888 KB Output is correct
3 Correct 45 ms 91852 KB Output is correct
4 Correct 45 ms 91816 KB Output is correct
5 Correct 58 ms 91928 KB Output is correct
6 Correct 48 ms 91860 KB Output is correct
7 Correct 52 ms 91932 KB Output is correct
8 Correct 47 ms 91876 KB Output is correct
9 Correct 44 ms 91980 KB Output is correct
10 Correct 46 ms 92116 KB Output is correct
11 Correct 47 ms 92228 KB Output is correct
12 Correct 45 ms 92176 KB Output is correct
13 Correct 52 ms 92204 KB Output is correct
14 Correct 45 ms 92240 KB Output is correct
15 Correct 51 ms 92308 KB Output is correct
16 Correct 62 ms 92764 KB Output is correct
17 Correct 69 ms 95440 KB Output is correct
18 Correct 100 ms 99840 KB Output is correct
19 Correct 79 ms 100936 KB Output is correct
20 Correct 79 ms 101068 KB Output is correct
21 Correct 53 ms 93728 KB Output is correct
22 Correct 76 ms 100044 KB Output is correct
23 Correct 90 ms 99256 KB Output is correct
24 Correct 80 ms 100708 KB Output is correct
25 Correct 77 ms 101196 KB Output is correct
26 Correct 78 ms 101072 KB Output is correct
27 Correct 80 ms 101032 KB Output is correct
28 Correct 82 ms 101068 KB Output is correct
29 Correct 90 ms 101016 KB Output is correct
30 Correct 85 ms 101056 KB Output is correct
31 Correct 88 ms 101052 KB Output is correct
32 Correct 92 ms 101000 KB Output is correct
33 Correct 106 ms 101140 KB Output is correct
34 Correct 108 ms 101184 KB Output is correct
35 Correct 92 ms 99800 KB Output is correct
36 Correct 67 ms 97144 KB Output is correct
37 Correct 119 ms 102180 KB Output is correct
38 Correct 138 ms 102556 KB Output is correct
39 Correct 137 ms 102568 KB Output is correct
40 Correct 144 ms 102624 KB Output is correct
41 Correct 130 ms 102556 KB Output is correct
42 Correct 89 ms 101568 KB Output is correct
43 Correct 98 ms 101404 KB Output is correct
44 Correct 96 ms 101500 KB Output is correct
45 Correct 165 ms 104160 KB Output is correct
46 Correct 151 ms 104084 KB Output is correct
47 Correct 452 ms 152592 KB Output is correct
48 Correct 365 ms 199032 KB Output is correct
49 Correct 394 ms 208664 KB Output is correct
50 Correct 469 ms 219860 KB Output is correct
51 Correct 588 ms 231388 KB Output is correct
52 Correct 587 ms 231532 KB Output is correct
53 Correct 508 ms 229396 KB Output is correct
54 Correct 463 ms 228332 KB Output is correct
55 Correct 466 ms 228448 KB Output is correct
56 Correct 484 ms 229636 KB Output is correct
57 Correct 657 ms 228448 KB Output is correct
58 Correct 471 ms 228844 KB Output is correct
59 Correct 461 ms 228916 KB Output is correct
60 Correct 545 ms 229292 KB Output is correct
61 Correct 491 ms 229020 KB Output is correct
62 Correct 556 ms 231456 KB Output is correct
63 Correct 612 ms 247228 KB Output is correct
64 Correct 592 ms 253516 KB Output is correct
65 Correct 825 ms 256668 KB Output is correct
66 Execution timed out 1084 ms 259360 KB Time limit exceeded
67 Halted 0 ms 0 KB -