oj.uz

Submission #881408

# Submission time Handle Problem Language Result Execution time Memory
881408 2023-12-01T08:29:53 Z cpptowin Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 971 ms 261244 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 30010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1 << j))
#define onbit(i, j) (i | (1 << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 200;
int n, m;
pii a[maxn];
int d[maxn][nsqrt + 1];
vector<array<int, 3>> ke[maxn][nsqrt + 1];
vi adj[maxn];
void dij(pii inp)
{
    fo(i, 0, maxn - 1) fo(j, 0, nsqrt - 1) d[i][j] = inf;
    d[inp.fi][inp.se] = 0;
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> q;
    q.push({0, inp});
    while (q.size())
    {
        int du = q.top().fi;
        int i = q.top().se.fi;
        int j = q.top().se.se;
        q.pop();
        if (du != d[i][j])
            continue;
        for (auto [i1, j1, w] : ke[i][j])
        {
            if (d[i1][j1] > du + w)
            {
                d[i1][j1] = du + w;
                q.push({d[i1][j1], {i1, j1}});
            }
        }
        if (i + j <= n and d[i + j][j] > du + 1)
        {
            d[i + j][j] = du + 1;
            q.push({du + 1, {i + j, j}});
        }
        if (i - j > 0 and d[i - j][j] > du + 1)
        {
            d[i - j][j] = du + 1;
            q.push({du + 1, {i - j, j}});
        }
        if (d[i][0] > du)
        {
            d[i][0] = du;
            q.push({du, {i, 0}});
        }
    }
}
vi save1[maxn];
bool used[maxn];
int s,t;
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    vi v;
    fo(i, 1, m)
    {
        cin >> a[i].fi >> a[i].se;
        a[i].fi++;
        if (a[i].se <= nsqrt and a[i].se)
        ke[a[i].fi][0].push_back({a[i].fi,a[i].se,0});
        else
            save1[a[i].fi].pb(a[i].se);
        v.pb(a[i].fi);
    }
    s = a[1].fi,t = a[2].fi;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int it : v)
    {
        if (save1[it].empty())
            continue;
        for (int i : save1[it])
            if (!used[i] and i > 0)
            {
                used[i] = 1;
                int pos = it;
                while (pos - i > 0)
                {
                    ke[it][0].push_back({pos - i, 0, (it - pos) / i + 1});
                    pos -= i;
                }
                pos = it;
                while (pos + i <= n)
                {
                    ke[it][0].push_back({pos + i, 0, (pos - it) / i + 1});
                    pos += i;
                }
            }
        for (int i : save1[it])
            used[i] = 0;
    }
    dij({s, 0});
    cout << (d[t][0] == inf ? -1 : d[t][0]);
}

Compilation message

skyscraper.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main()
      | ^~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 190720 KB Output is correct
2 Correct 52 ms 190544 KB Output is correct
3 Correct 53 ms 190612 KB Output is correct
4 Correct 53 ms 190544 KB Output is correct
5 Correct 52 ms 190504 KB Output is correct
6 Correct 56 ms 190840 KB Output is correct
7 Correct 52 ms 190548 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 190508 KB Output is correct
2 Correct 53 ms 190544 KB Output is correct
3 Correct 54 ms 190544 KB Output is correct
4 Correct 54 ms 190724 KB Output is correct
5 Correct 53 ms 190544 KB Output is correct
6 Correct 52 ms 190548 KB Output is correct
7 Correct 54 ms 190580 KB Output is correct
8 Correct 53 ms 190744 KB Output is correct
9 Correct 53 ms 190592 KB Output is correct
10 Correct 57 ms 190768 KB Output is correct
11 Correct 52 ms 190832 KB Output is correct
12 Correct 52 ms 190804 KB Output is correct
13 Correct 54 ms 190820 KB Output is correct
14 Correct 54 ms 190800 KB Output is correct
15 Correct 55 ms 190812 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 190544 KB Output is correct
2 Correct 52 ms 190544 KB Output is correct
3 Correct 53 ms 190544 KB Output is correct
4 Correct 53 ms 190548 KB Output is correct
5 Correct 51 ms 190544 KB Output is correct
6 Correct 53 ms 190612 KB Output is correct
7 Correct 55 ms 190544 KB Output is correct
8 Correct 51 ms 190544 KB Output is correct
9 Correct 53 ms 190728 KB Output is correct
10 Correct 52 ms 190552 KB Output is correct
11 Correct 53 ms 190804 KB Output is correct
12 Correct 52 ms 190812 KB Output is correct
13 Correct 52 ms 190896 KB Output is correct
14 Correct 53 ms 190796 KB Output is correct
15 Correct 53 ms 190880 KB Output is correct
16 Correct 52 ms 190616 KB Output is correct
17 Correct 54 ms 190760 KB Output is correct
18 Correct 51 ms 190620 KB Output is correct
19 Correct 52 ms 190796 KB Output is correct
20 Correct 52 ms 190852 KB Output is correct
21 Correct 53 ms 190804 KB Output is correct
22 Correct 52 ms 190800 KB Output is correct
23 Correct 52 ms 190804 KB Output is correct
24 Correct 55 ms 190804 KB Output is correct
25 Correct 53 ms 190800 KB Output is correct
26 Correct 52 ms 190884 KB Output is correct
27 Correct 52 ms 190652 KB Output is correct
28 Correct 55 ms 190804 KB Output is correct
29 Correct 59 ms 190768 KB Output is correct
30 Correct 57 ms 190548 KB Output is correct
31 Correct 56 ms 190804 KB Output is correct
32 Correct 54 ms 190544 KB Output is correct
33 Correct 65 ms 190784 KB Output is correct
34 Correct 65 ms 190968 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 190548 KB Output is correct
2 Correct 52 ms 190544 KB Output is correct
3 Correct 58 ms 190548 KB Output is correct
4 Correct 54 ms 190724 KB Output is correct
5 Correct 52 ms 190544 KB Output is correct
6 Correct 52 ms 190544 KB Output is correct
7 Correct 54 ms 190524 KB Output is correct
8 Correct 54 ms 190728 KB Output is correct
9 Correct 51 ms 190552 KB Output is correct
10 Correct 53 ms 190548 KB Output is correct
11 Correct 54 ms 190804 KB Output is correct
12 Correct 52 ms 190864 KB Output is correct
13 Correct 52 ms 190776 KB Output is correct
14 Correct 58 ms 191188 KB Output is correct
15 Correct 54 ms 190804 KB Output is correct
16 Correct 52 ms 190592 KB Output is correct
17 Correct 55 ms 190804 KB Output is correct
18 Correct 53 ms 190664 KB Output is correct
19 Correct 53 ms 190548 KB Output is correct
20 Correct 53 ms 190800 KB Output is correct
21 Correct 53 ms 190800 KB Output is correct
22 Correct 53 ms 190804 KB Output is correct
23 Correct 53 ms 190804 KB Output is correct
24 Correct 55 ms 190804 KB Output is correct
25 Correct 56 ms 191028 KB Output is correct
26 Correct 56 ms 190800 KB Output is correct
27 Correct 53 ms 190804 KB Output is correct
28 Correct 54 ms 190812 KB Output is correct
29 Correct 59 ms 190800 KB Output is correct
30 Correct 54 ms 190548 KB Output is correct
31 Correct 57 ms 190884 KB Output is correct
32 Correct 56 ms 190764 KB Output is correct
33 Correct 68 ms 190804 KB Output is correct
34 Correct 65 ms 190784 KB Output is correct
35 Correct 69 ms 193064 KB Output is correct
36 Correct 56 ms 191056 KB Output is correct
37 Correct 79 ms 193756 KB Output is correct
38 Correct 74 ms 193916 KB Output is correct
39 Correct 74 ms 194068 KB Output is correct
40 Correct 75 ms 193884 KB Output is correct
41 Correct 74 ms 194012 KB Output is correct
42 Correct 58 ms 192516 KB Output is correct
43 Correct 54 ms 192396 KB Output is correct
44 Correct 57 ms 192280 KB Output is correct
45 Correct 111 ms 195800 KB Output is correct
46 Correct 112 ms 195540 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 190804 KB Output is correct
2 Correct 53 ms 190724 KB Output is correct
3 Correct 52 ms 190612 KB Output is correct
4 Correct 51 ms 190548 KB Output is correct
5 Correct 52 ms 190540 KB Output is correct
6 Correct 54 ms 191096 KB Output is correct
7 Correct 51 ms 190544 KB Output is correct
8 Correct 53 ms 190548 KB Output is correct
9 Correct 54 ms 190672 KB Output is correct
10 Correct 60 ms 190776 KB Output is correct
11 Correct 60 ms 190800 KB Output is correct
12 Correct 63 ms 190816 KB Output is correct
13 Correct 61 ms 190804 KB Output is correct
14 Correct 59 ms 190932 KB Output is correct
15 Correct 61 ms 190800 KB Output is correct
16 Correct 59 ms 190768 KB Output is correct
17 Correct 62 ms 190800 KB Output is correct
18 Correct 61 ms 190804 KB Output is correct
19 Correct 60 ms 190804 KB Output is correct
20 Correct 61 ms 190800 KB Output is correct
21 Correct 61 ms 190608 KB Output is correct
22 Correct 59 ms 190808 KB Output is correct
23 Correct 60 ms 190800 KB Output is correct
24 Correct 61 ms 190944 KB Output is correct
25 Correct 62 ms 190804 KB Output is correct
26 Correct 60 ms 190772 KB Output is correct
27 Correct 60 ms 191056 KB Output is correct
28 Correct 63 ms 190804 KB Output is correct
29 Correct 66 ms 190704 KB Output is correct
30 Correct 60 ms 190556 KB Output is correct
31 Correct 62 ms 190804 KB Output is correct
32 Correct 61 ms 190848 KB Output is correct
33 Correct 72 ms 190804 KB Output is correct
34 Correct 72 ms 190804 KB Output is correct
35 Correct 75 ms 192972 KB Output is correct
36 Correct 62 ms 191060 KB Output is correct
37 Correct 84 ms 193568 KB Output is correct
38 Correct 83 ms 193984 KB Output is correct
39 Correct 82 ms 194064 KB Output is correct
40 Correct 82 ms 193920 KB Output is correct
41 Correct 82 ms 193972 KB Output is correct
42 Correct 64 ms 192516 KB Output is correct
43 Correct 64 ms 192392 KB Output is correct
44 Correct 63 ms 192516 KB Output is correct
45 Correct 117 ms 195800 KB Output is correct
46 Correct 119 ms 195792 KB Output is correct
47 Correct 167 ms 202816 KB Output is correct
48 Correct 70 ms 194696 KB Output is correct
49 Correct 68 ms 194216 KB Output is correct
50 Correct 68 ms 193364 KB Output is correct
51 Correct 118 ms 197328 KB Output is correct
52 Correct 123 ms 197424 KB Output is correct
53 Correct 74 ms 192436 KB Output is correct
54 Correct 60 ms 190632 KB Output is correct
55 Correct 61 ms 190520 KB Output is correct
56 Correct 75 ms 192460 KB Output is correct
57 Correct 150 ms 190912 KB Output is correct
58 Correct 72 ms 192228 KB Output is correct
59 Correct 73 ms 192524 KB Output is correct
60 Correct 79 ms 192928 KB Output is correct
61 Correct 75 ms 192844 KB Output is correct
62 Correct 119 ms 198864 KB Output is correct
63 Correct 166 ms 249160 KB Output is correct
64 Correct 167 ms 261244 KB Output is correct
65 Correct 531 ms 252228 KB Output is correct
66 Correct 970 ms 227752 KB Output is correct
67 Correct 971 ms 227828 KB Output is correct