oj.uz

Submission #709863

# Submission time Handle Problem Language Result Execution time Memory
709863 2023-03-14T17:54:25 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 151 ms 223832 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; j + d[i].second < n; j += d[i].second)
        {
            g[j][0].push_back({j + d[i].second, 0, 1});
            g[j + d[i].second][0].push_back({j, 0, 1});
        }
    }
    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

# Verdict Execution time Memory Grader output
1 Correct 98 ms 211576 KB Output is correct
2 Correct 94 ms 211552 KB Output is correct
3 Correct 107 ms 211620 KB Output is correct
4 Correct 113 ms 211660 KB Output is correct
5 Correct 116 ms 211676 KB Output is correct
6 Correct 114 ms 211612 KB Output is correct
7 Correct 118 ms 211680 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 211592 KB Output is correct
2 Correct 114 ms 211620 KB Output is correct
3 Correct 118 ms 211776 KB Output is correct
4 Correct 94 ms 211672 KB Output is correct
5 Correct 99 ms 211620 KB Output is correct
6 Correct 97 ms 211596 KB Output is correct
7 Correct 95 ms 211716 KB Output is correct
8 Correct 96 ms 211744 KB Output is correct
9 Correct 94 ms 211752 KB Output is correct
10 Correct 95 ms 212028 KB Output is correct
11 Correct 95 ms 212236 KB Output is correct
12 Correct 94 ms 212204 KB Output is correct
13 Correct 98 ms 212124 KB Output is correct
14 Correct 97 ms 212272 KB Output is correct
15 Correct 105 ms 212180 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 211676 KB Output is correct
2 Correct 96 ms 211696 KB Output is correct
3 Correct 96 ms 211668 KB Output is correct
4 Correct 92 ms 211660 KB Output is correct
5 Correct 98 ms 211676 KB Output is correct
6 Correct 96 ms 211572 KB Output is correct
7 Correct 95 ms 211712 KB Output is correct
8 Correct 94 ms 211784 KB Output is correct
9 Correct 100 ms 211800 KB Output is correct
10 Correct 100 ms 212032 KB Output is correct
11 Correct 97 ms 212204 KB Output is correct
12 Correct 99 ms 212044 KB Output is correct
13 Correct 108 ms 212156 KB Output is correct
14 Correct 100 ms 212152 KB Output is correct
15 Correct 99 ms 212172 KB Output is correct
16 Correct 102 ms 213068 KB Output is correct
17 Incorrect 128 ms 223788 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 211560 KB Output is correct
2 Correct 97 ms 211600 KB Output is correct
3 Correct 113 ms 211668 KB Output is correct
4 Correct 96 ms 211596 KB Output is correct
5 Correct 94 ms 211680 KB Output is correct
6 Correct 94 ms 211652 KB Output is correct
7 Correct 94 ms 211644 KB Output is correct
8 Correct 94 ms 211724 KB Output is correct
9 Correct 104 ms 211764 KB Output is correct
10 Correct 96 ms 212044 KB Output is correct
11 Correct 97 ms 212208 KB Output is correct
12 Correct 97 ms 212060 KB Output is correct
13 Correct 97 ms 212036 KB Output is correct
14 Correct 104 ms 212276 KB Output is correct
15 Correct 98 ms 212284 KB Output is correct
16 Correct 109 ms 213084 KB Output is correct
17 Incorrect 124 ms 223832 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 211560 KB Output is correct
2 Correct 103 ms 211584 KB Output is correct
3 Correct 109 ms 211664 KB Output is correct
4 Correct 101 ms 211772 KB Output is correct
5 Correct 103 ms 211660 KB Output is correct
6 Correct 151 ms 211624 KB Output is correct
7 Correct 102 ms 211592 KB Output is correct
8 Correct 117 ms 211736 KB Output is correct
9 Correct 105 ms 211788 KB Output is correct
10 Correct 103 ms 212128 KB Output is correct
11 Correct 98 ms 212172 KB Output is correct
12 Correct 100 ms 212048 KB Output is correct
13 Correct 99 ms 212144 KB Output is correct
14 Correct 121 ms 212212 KB Output is correct
15 Correct 106 ms 212168 KB Output is correct
16 Correct 100 ms 213196 KB Output is correct
17 Incorrect 138 ms 223720 KB Output isn't correct
18 Halted 0 ms 0 KB -