oj.uz

답안 #709867

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

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 = 0; 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());
        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 99 ms 211560 KB Output is correct
2 Correct 98 ms 211596 KB Output is correct
3 Correct 106 ms 211752 KB Output is correct
4 Correct 98 ms 211672 KB Output is correct
5 Correct 98 ms 211660 KB Output is correct
6 Correct 104 ms 211660 KB Output is correct
7 Correct 108 ms 211676 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 211604 KB Output is correct
2 Correct 96 ms 211564 KB Output is correct
3 Correct 102 ms 211620 KB Output is correct
4 Correct 111 ms 211672 KB Output is correct
5 Correct 98 ms 211656 KB Output is correct
6 Correct 100 ms 211724 KB Output is correct
7 Correct 106 ms 211588 KB Output is correct
8 Correct 106 ms 211748 KB Output is correct
9 Correct 99 ms 211800 KB Output is correct
10 Correct 99 ms 212008 KB Output is correct
11 Correct 100 ms 212200 KB Output is correct
12 Correct 103 ms 212140 KB Output is correct
13 Correct 110 ms 212228 KB Output is correct
14 Correct 113 ms 212276 KB Output is correct
15 Correct 101 ms 212176 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 211572 KB Output is correct
2 Correct 103 ms 211660 KB Output is correct
3 Correct 114 ms 211664 KB Output is correct
4 Correct 99 ms 211656 KB Output is correct
5 Correct 100 ms 211660 KB Output is correct
6 Correct 97 ms 211744 KB Output is correct
7 Correct 96 ms 211616 KB Output is correct
8 Correct 102 ms 211636 KB Output is correct
9 Correct 100 ms 211792 KB Output is correct
10 Correct 108 ms 212088 KB Output is correct
11 Correct 115 ms 212272 KB Output is correct
12 Correct 97 ms 212080 KB Output is correct
13 Correct 102 ms 212064 KB Output is correct
14 Correct 98 ms 212256 KB Output is correct
15 Correct 109 ms 212176 KB Output is correct
16 Correct 121 ms 213172 KB Output is correct
17 Correct 126 ms 223820 KB Output is correct
18 Correct 156 ms 243872 KB Output is correct
19 Correct 168 ms 248776 KB Output is correct
20 Correct 164 ms 248908 KB Output is correct
21 Correct 112 ms 216780 KB Output is correct
22 Correct 167 ms 244428 KB Output is correct
23 Correct 162 ms 240844 KB Output is correct
24 Correct 172 ms 246924 KB Output is correct
25 Correct 169 ms 248916 KB Output is correct
26 Correct 170 ms 248808 KB Output is correct
27 Correct 174 ms 248780 KB Output is correct
28 Correct 173 ms 248948 KB Output is correct
29 Correct 188 ms 248796 KB Output is correct
30 Correct 168 ms 248800 KB Output is correct
31 Correct 177 ms 248780 KB Output is correct
32 Correct 167 ms 248940 KB Output is correct
33 Correct 195 ms 248936 KB Output is correct
34 Correct 195 ms 249016 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 211684 KB Output is correct
2 Correct 97 ms 211580 KB Output is correct
3 Correct 96 ms 211628 KB Output is correct
4 Correct 105 ms 211676 KB Output is correct
5 Correct 96 ms 211668 KB Output is correct
6 Correct 103 ms 211620 KB Output is correct
7 Correct 99 ms 211620 KB Output is correct
8 Correct 99 ms 211644 KB Output is correct
9 Correct 99 ms 211816 KB Output is correct
10 Correct 102 ms 212124 KB Output is correct
11 Correct 119 ms 212180 KB Output is correct
12 Correct 102 ms 212132 KB Output is correct
13 Correct 99 ms 212044 KB Output is correct
14 Correct 101 ms 212200 KB Output is correct
15 Correct 102 ms 212224 KB Output is correct
16 Correct 114 ms 213084 KB Output is correct
17 Correct 123 ms 223776 KB Output is correct
18 Correct 157 ms 243796 KB Output is correct
19 Correct 176 ms 248828 KB Output is correct
20 Correct 174 ms 248888 KB Output is correct
21 Correct 111 ms 216912 KB Output is correct
22 Correct 153 ms 244424 KB Output is correct
23 Correct 155 ms 240848 KB Output is correct
24 Correct 171 ms 247004 KB Output is correct
25 Correct 165 ms 249012 KB Output is correct
26 Correct 171 ms 248728 KB Output is correct
27 Correct 175 ms 248904 KB Output is correct
28 Correct 174 ms 248908 KB Output is correct
29 Correct 182 ms 248960 KB Output is correct
30 Correct 174 ms 248732 KB Output is correct
31 Correct 186 ms 248884 KB Output is correct
32 Correct 169 ms 248920 KB Output is correct
33 Correct 201 ms 248936 KB Output is correct
34 Correct 233 ms 248996 KB Output is correct
35 Correct 197 ms 239480 KB Output is correct
36 Correct 138 ms 230988 KB Output is correct
37 Correct 234 ms 249780 KB Output is correct
38 Correct 246 ms 251304 KB Output is correct
39 Correct 245 ms 251436 KB Output is correct
40 Correct 225 ms 251384 KB Output is correct
41 Correct 221 ms 251440 KB Output is correct
42 Correct 175 ms 249484 KB Output is correct
43 Correct 176 ms 249532 KB Output is correct
44 Correct 168 ms 249620 KB Output is correct
45 Correct 327 ms 251660 KB Output is correct
46 Correct 311 ms 251596 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 211664 KB Output is correct
2 Correct 103 ms 211672 KB Output is correct
3 Correct 98 ms 211576 KB Output is correct
4 Correct 99 ms 211548 KB Output is correct
5 Correct 99 ms 211660 KB Output is correct
6 Correct 106 ms 211672 KB Output is correct
7 Correct 98 ms 211660 KB Output is correct
8 Correct 97 ms 211660 KB Output is correct
9 Correct 116 ms 211728 KB Output is correct
10 Correct 115 ms 212104 KB Output is correct
11 Correct 109 ms 212164 KB Output is correct
12 Correct 99 ms 212144 KB Output is correct
13 Correct 100 ms 212032 KB Output is correct
14 Correct 103 ms 212172 KB Output is correct
15 Correct 101 ms 212208 KB Output is correct
16 Correct 102 ms 213300 KB Output is correct
17 Correct 126 ms 223868 KB Output is correct
18 Correct 164 ms 243716 KB Output is correct
19 Correct 164 ms 248732 KB Output is correct
20 Correct 165 ms 248840 KB Output is correct
21 Correct 108 ms 216692 KB Output is correct
22 Correct 162 ms 244528 KB Output is correct
23 Correct 152 ms 240884 KB Output is correct
24 Correct 170 ms 246888 KB Output is correct
25 Correct 169 ms 249040 KB Output is correct
26 Correct 164 ms 248840 KB Output is correct
27 Correct 172 ms 248944 KB Output is correct
28 Correct 175 ms 248964 KB Output is correct
29 Correct 190 ms 248872 KB Output is correct
30 Correct 170 ms 248800 KB Output is correct
31 Correct 176 ms 248804 KB Output is correct
32 Correct 180 ms 248992 KB Output is correct
33 Correct 197 ms 248840 KB Output is correct
34 Correct 214 ms 248964 KB Output is correct
35 Correct 188 ms 239616 KB Output is correct
36 Correct 141 ms 230944 KB Output is correct
37 Correct 227 ms 249804 KB Output is correct
38 Correct 224 ms 251348 KB Output is correct
39 Correct 224 ms 251468 KB Output is correct
40 Correct 220 ms 251500 KB Output is correct
41 Correct 237 ms 251496 KB Output is correct
42 Correct 176 ms 249544 KB Output is correct
43 Correct 171 ms 249476 KB Output is correct
44 Correct 169 ms 249648 KB Output is correct
45 Correct 334 ms 251528 KB Output is correct
46 Correct 323 ms 251640 KB Output is correct
47 Runtime error 172 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -