oj.uz

Submission #877891

# Submission time Handle Problem Language Result Execution time Memory
877891 2023-11-23T20:36:24 Z sysia Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 934 ms 252244 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

// #define int long long
typedef pair<int, int> T;
const int oo = 1e9+7, K = 30;
const int mod = 998244353;

const int S = 300;

void solve(){
    int n, m; cin >> n >> m;
    vector<vector<T>>g(n*S+2);
    auto ch = [&](int v, int j = 0){return v*S+j;};
    vector<vector<int>>doge(n+1);
    int start, kon;
    for (int i = 0; i<m; i++){
        int v, j; cin >> v >> j;
        if (i == 0) start = ch(v);  
        if (i == 1) kon = ch(v);
        // if (j >= n) continue;
        if (j < S) g[ch(v)].emplace_back(ch(v, j), 0);
        else doge[v].emplace_back(j);
    }
   
    vector<int>dist(n*S+2, oo);
    set<T>s;
    debug(start, kon);
    s.insert({0, start});
    dist[start] = 0;
    while ((int)s.size()){
        auto [d, v] = *s.begin();
        s.erase(s.begin());
        debug(v);
        if (dist[v] < d) continue; 
        auto popraw = [&](int what, int from, int c){
            debug(what, from, c);
            if (dist[what] > dist[from] + c){
                dist[what] = dist[from] + c;
                s.insert({dist[what], what});
            }
        }; 
        //dlugie skoki
        if (v%S == 0){
            int vv = v/S;
            for (auto j: doge[vv]){
                for (int u = vv-j, k = 1; u >= 0; u-=j, k++){
                    popraw(ch(u), v, k);
                }
                for (int u = vv+j, k = 1; u<n; u+=j, k++){
                    popraw(ch(u), v, k);
                }
            }
        }
        //jakies inne losowe
        for (auto [x, c]: g[v]){
            popraw(x, v, c);
        }
        //krotkie skoki
        int j = v%S;
        if (j != 0){
            int pos = v-v%S;
            popraw(pos, v, 0);
            int u = pos/S;
            debug(u, j);
            if (u >= j){
                popraw(ch(u-j, j), v, 1);
            }
            if (u + j < n){
                popraw(ch(u+j, j), v, 1);
            }
        }
    }
    int ans = dist[kon];
    if (ans == oo) ans = -1;
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Compilation message

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:97:23: warning: 'kon' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |     int ans = dist[kon];
      |                       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 2 ms 1372 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 860 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 2 ms 1372 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct
17 Correct 6 ms 6492 KB Output is correct
18 Correct 4 ms 14684 KB Output is correct
19 Correct 4 ms 16732 KB Output is correct
20 Correct 5 ms 16988 KB Output is correct
21 Correct 2 ms 3680 KB Output is correct
22 Correct 5 ms 14940 KB Output is correct
23 Correct 4 ms 13660 KB Output is correct
24 Correct 6 ms 16012 KB Output is correct
25 Correct 5 ms 16988 KB Output is correct
26 Correct 6 ms 16988 KB Output is correct
27 Correct 5 ms 16988 KB Output is correct
28 Correct 8 ms 16868 KB Output is correct
29 Correct 11 ms 16984 KB Output is correct
30 Correct 7 ms 16732 KB Output is correct
31 Correct 8 ms 16836 KB Output is correct
32 Correct 7 ms 16732 KB Output is correct
33 Correct 18 ms 16988 KB Output is correct
34 Correct 16 ms 16944 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 2 ms 1372 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 1 ms 2140 KB Output is correct
17 Correct 4 ms 6492 KB Output is correct
18 Correct 5 ms 14684 KB Output is correct
19 Correct 4 ms 16732 KB Output is correct
20 Correct 5 ms 16988 KB Output is correct
21 Correct 2 ms 3676 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 6 ms 13656 KB Output is correct
24 Correct 6 ms 15960 KB Output is correct
25 Correct 5 ms 16988 KB Output is correct
26 Correct 5 ms 16988 KB Output is correct
27 Correct 5 ms 16820 KB Output is correct
28 Correct 6 ms 16984 KB Output is correct
29 Correct 12 ms 16988 KB Output is correct
30 Correct 6 ms 16732 KB Output is correct
31 Correct 8 ms 16836 KB Output is correct
32 Correct 7 ms 16728 KB Output is correct
33 Correct 16 ms 16988 KB Output is correct
34 Correct 17 ms 16988 KB Output is correct
35 Correct 17 ms 12892 KB Output is correct
36 Correct 5 ms 9564 KB Output is correct
37 Correct 28 ms 17252 KB Output is correct
38 Correct 25 ms 17848 KB Output is correct
39 Correct 29 ms 17836 KB Output is correct
40 Correct 26 ms 17828 KB Output is correct
41 Correct 28 ms 17760 KB Output is correct
42 Correct 8 ms 17364 KB Output is correct
43 Correct 10 ms 17444 KB Output is correct
44 Correct 9 ms 17508 KB Output is correct
45 Correct 72 ms 18892 KB Output is correct
46 Correct 71 ms 18776 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 352 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 860 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1368 KB Output is correct
14 Correct 2 ms 1372 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct
17 Correct 4 ms 6488 KB Output is correct
18 Correct 4 ms 14680 KB Output is correct
19 Correct 4 ms 16732 KB Output is correct
20 Correct 5 ms 16988 KB Output is correct
21 Correct 2 ms 3676 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 6 ms 13692 KB Output is correct
24 Correct 6 ms 16220 KB Output is correct
25 Correct 5 ms 16988 KB Output is correct
26 Correct 7 ms 16984 KB Output is correct
27 Correct 5 ms 17008 KB Output is correct
28 Correct 6 ms 16988 KB Output is correct
29 Correct 11 ms 16808 KB Output is correct
30 Correct 6 ms 16732 KB Output is correct
31 Correct 8 ms 16988 KB Output is correct
32 Correct 7 ms 16988 KB Output is correct
33 Correct 16 ms 16988 KB Output is correct
34 Correct 18 ms 16868 KB Output is correct
35 Correct 16 ms 12888 KB Output is correct
36 Correct 5 ms 9564 KB Output is correct
37 Correct 28 ms 17336 KB Output is correct
38 Correct 26 ms 17756 KB Output is correct
39 Correct 25 ms 17756 KB Output is correct
40 Correct 27 ms 17848 KB Output is correct
41 Correct 26 ms 17756 KB Output is correct
42 Correct 8 ms 17360 KB Output is correct
43 Correct 8 ms 17364 KB Output is correct
44 Correct 7 ms 17368 KB Output is correct
45 Correct 73 ms 18900 KB Output is correct
46 Correct 72 ms 18896 KB Output is correct
47 Correct 131 ms 103768 KB Output is correct
48 Correct 61 ms 192536 KB Output is correct
49 Correct 50 ms 210256 KB Output is correct
50 Correct 57 ms 230996 KB Output is correct
51 Correct 118 ms 249324 KB Output is correct
52 Correct 118 ms 249428 KB Output is correct
53 Correct 75 ms 248660 KB Output is correct
54 Correct 66 ms 247836 KB Output is correct
55 Correct 68 ms 247632 KB Output is correct
56 Correct 75 ms 248792 KB Output is correct
57 Correct 171 ms 247856 KB Output is correct
58 Correct 74 ms 248024 KB Output is correct
59 Correct 77 ms 248224 KB Output is correct
60 Correct 93 ms 248316 KB Output is correct
61 Correct 80 ms 248332 KB Output is correct
62 Correct 117 ms 248852 KB Output is correct
63 Correct 250 ms 252244 KB Output is correct
64 Correct 361 ms 252204 KB Output is correct
65 Correct 835 ms 252236 KB Output is correct
66 Correct 934 ms 249692 KB Output is correct
67 Correct 876 ms 249696 KB Output is correct