oj.uz

Submission #709871

# Submission time Handle Problem Language Result Execution time Memory
709871 2023-03-14T18:19:46 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 140 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 = 173;
const int MAXN = 3e4 + 5;

vector<pair<int, int> > d;

int dist[MAXN][B];
set<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].insert({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].insert({i - j, 0, 1});
                g[i][j].insert({i - j, j, 1});
            }
            if (i + j < n)
            {
                g[i][j].insert({i + j, 0, 1});
                g[i][j].insert({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].insert({j, 0, k});
        }
        for (int j = d[i].first, k = 0; j >= 0; j -= d[i].second,  k++)
        {
            g[d[i].first][0].insert({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

# Verdict Execution time Memory Grader output
1 Correct 106 ms 244016 KB Output is correct
2 Correct 108 ms 243996 KB Output is correct
3 Correct 114 ms 244044 KB Output is correct
4 Correct 106 ms 244040 KB Output is correct
5 Correct 108 ms 244104 KB Output is correct
6 Correct 112 ms 244028 KB Output is correct
7 Correct 106 ms 244044 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 244100 KB Output is correct
2 Correct 104 ms 243992 KB Output is correct
3 Correct 113 ms 244096 KB Output is correct
4 Correct 119 ms 244044 KB Output is correct
5 Correct 105 ms 244048 KB Output is correct
6 Correct 114 ms 244120 KB Output is correct
7 Correct 107 ms 244044 KB Output is correct
8 Correct 106 ms 244364 KB Output is correct
9 Correct 111 ms 244464 KB Output is correct
10 Correct 114 ms 245448 KB Output is correct
11 Correct 113 ms 245516 KB Output is correct
12 Correct 107 ms 245324 KB Output is correct
13 Correct 105 ms 245416 KB Output is correct
14 Correct 109 ms 245640 KB Output is correct
15 Correct 107 ms 245652 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 244020 KB Output is correct
2 Correct 107 ms 244044 KB Output is correct
3 Correct 104 ms 244044 KB Output is correct
4 Correct 110 ms 244040 KB Output is correct
5 Correct 120 ms 244124 KB Output is correct
6 Correct 125 ms 244032 KB Output is correct
7 Correct 115 ms 244116 KB Output is correct
8 Correct 112 ms 244288 KB Output is correct
9 Correct 113 ms 244556 KB Output is correct
10 Correct 116 ms 245376 KB Output is correct
11 Correct 127 ms 245548 KB Output is correct
12 Correct 133 ms 245436 KB Output is correct
13 Correct 126 ms 245316 KB Output is correct
14 Correct 138 ms 245672 KB Output is correct
15 Correct 125 ms 245580 KB Output is correct
16 Correct 133 ms 249192 KB Output is correct
17 Runtime error 124 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 244000 KB Output is correct
2 Correct 103 ms 244084 KB Output is correct
3 Correct 123 ms 244104 KB Output is correct
4 Correct 107 ms 244100 KB Output is correct
5 Correct 106 ms 244120 KB Output is correct
6 Correct 125 ms 244116 KB Output is correct
7 Correct 108 ms 244088 KB Output is correct
8 Correct 115 ms 244284 KB Output is correct
9 Correct 108 ms 244516 KB Output is correct
10 Correct 117 ms 245348 KB Output is correct
11 Correct 117 ms 245488 KB Output is correct
12 Correct 110 ms 245532 KB Output is correct
13 Correct 119 ms 245480 KB Output is correct
14 Correct 110 ms 245620 KB Output is correct
15 Correct 113 ms 245572 KB Output is correct
16 Correct 124 ms 249100 KB Output is correct
17 Runtime error 112 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 244068 KB Output is correct
2 Correct 123 ms 244040 KB Output is correct
3 Correct 105 ms 244072 KB Output is correct
4 Correct 106 ms 244228 KB Output is correct
5 Correct 117 ms 244044 KB Output is correct
6 Correct 109 ms 244008 KB Output is correct
7 Correct 107 ms 244148 KB Output is correct
8 Correct 109 ms 244172 KB Output is correct
9 Correct 126 ms 244536 KB Output is correct
10 Correct 116 ms 245348 KB Output is correct
11 Correct 112 ms 245708 KB Output is correct
12 Correct 112 ms 245428 KB Output is correct
13 Correct 113 ms 245340 KB Output is correct
14 Correct 112 ms 245580 KB Output is correct
15 Correct 110 ms 245592 KB Output is correct
16 Correct 115 ms 249152 KB Output is correct
17 Runtime error 140 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -