oj.uz

Submission #705519

# Submission time Handle Problem Language Result Execution time Memory
705519 2023-03-04T15:11:48 Z Alihan_8 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 102 ms 262144 KB 
#include <bits/stdc++.h>
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define int long long
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m; cin >> n >> m;
    vector <int> g[n];
    const int N = 2e3+1;
    vector <vector<int>> dis(n, vector <int> (N, -1));
    queue <pair<int,int>> q;
    int en = -1, st = -1;
    for ( int i = 1; i <= m; i++ ){
        int pos, val; cin >> pos >> val;
        if ( i == 1 ) st = pos;
        if ( i == 2 ) en = pos;
        g[pos].pb(val);
    }
    for ( auto i: g[st] ){
        dis[st][i] = 0;
        q.push({st, i});
    }
    while ( !q.empty() ){
        auto [cur, val] = q.front();
        q.pop();
        if ( cur == en ){
            cout << dis[cur][val] << ln;
            return 0;
        }
        for ( auto sign: {-1, 1} ){
            int to = cur-val*sign;
            if ( to >= 0 and to < n ){
                if ( dis[to][val] == -1 ){
                    dis[to][val] = dis[cur][val]+1;
                    q.push({to, val});
                }
                for ( auto w: g[to] ){
                    if ( dis[to][w] != -1 ) continue;
                    dis[to][w] = dis[cur][val]+1;
                    q.push({to, w});
                }
            }
        }
    }
    cout << "-1";

    cout << '\n';
}
/*
5 3
0 2
1 1
4 1
*/

Compilation message

skyscraper.cpp: In function 'void IO(std::string)':
skyscraper.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 2 ms 1904 KB Output is correct
15 Correct 2 ms 1876 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 2 ms 1912 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct
15 Correct 1 ms 1876 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 5 ms 11988 KB Output is correct
18 Correct 12 ms 27732 KB Output is correct
19 Correct 12 ms 31676 KB Output is correct
20 Correct 15 ms 31828 KB Output is correct
21 Correct 3 ms 6472 KB Output is correct
22 Correct 11 ms 28224 KB Output is correct
23 Correct 10 ms 25416 KB Output is correct
24 Correct 13 ms 30164 KB Output is correct
25 Correct 17 ms 31736 KB Output is correct
26 Correct 17 ms 31748 KB Output is correct
27 Correct 14 ms 31700 KB Output is correct
28 Correct 14 ms 31828 KB Output is correct
29 Correct 14 ms 31684 KB Output is correct
30 Correct 13 ms 31640 KB Output is correct
31 Correct 14 ms 31700 KB Output is correct
32 Correct 16 ms 31764 KB Output is correct
33 Correct 17 ms 31816 KB Output is correct
34 Correct 15 ms 31700 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 1 ms 1876 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct
15 Correct 1 ms 1876 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Correct 11 ms 27732 KB Output is correct
19 Correct 14 ms 31684 KB Output is correct
20 Correct 13 ms 31756 KB Output is correct
21 Correct 4 ms 6484 KB Output is correct
22 Correct 14 ms 28256 KB Output is correct
23 Correct 11 ms 25372 KB Output is correct
24 Correct 14 ms 30164 KB Output is correct
25 Correct 13 ms 31700 KB Output is correct
26 Correct 13 ms 31692 KB Output is correct
27 Correct 14 ms 31708 KB Output is correct
28 Correct 14 ms 31740 KB Output is correct
29 Correct 14 ms 31812 KB Output is correct
30 Correct 16 ms 31716 KB Output is correct
31 Correct 14 ms 31684 KB Output is correct
32 Correct 13 ms 31700 KB Output is correct
33 Correct 16 ms 31736 KB Output is correct
34 Correct 17 ms 31828 KB Output is correct
35 Correct 20 ms 23804 KB Output is correct
36 Correct 9 ms 17492 KB Output is correct
37 Correct 23 ms 31500 KB Output is correct
38 Correct 24 ms 32880 KB Output is correct
39 Correct 17 ms 32468 KB Output is correct
40 Correct 19 ms 32580 KB Output is correct
41 Correct 19 ms 32816 KB Output is correct
42 Correct 16 ms 32336 KB Output is correct
43 Correct 16 ms 32340 KB Output is correct
44 Correct 17 ms 32324 KB Output is correct
45 Correct 49 ms 32784 KB Output is correct
46 Correct 36 ms 32704 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 1 ms 1876 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct
15 Correct 1 ms 1876 KB Output is correct
16 Correct 2 ms 3412 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Correct 11 ms 27732 KB Output is correct
19 Correct 15 ms 31656 KB Output is correct
20 Correct 13 ms 31828 KB Output is correct
21 Correct 3 ms 6484 KB Output is correct
22 Correct 13 ms 28244 KB Output is correct
23 Correct 12 ms 25428 KB Output is correct
24 Correct 13 ms 30164 KB Output is correct
25 Correct 13 ms 31824 KB Output is correct
26 Correct 12 ms 31700 KB Output is correct
27 Correct 13 ms 31796 KB Output is correct
28 Correct 14 ms 31828 KB Output is correct
29 Correct 14 ms 31700 KB Output is correct
30 Correct 13 ms 31700 KB Output is correct
31 Correct 14 ms 31708 KB Output is correct
32 Correct 14 ms 31700 KB Output is correct
33 Correct 17 ms 31736 KB Output is correct
34 Correct 16 ms 31832 KB Output is correct
35 Correct 21 ms 23820 KB Output is correct
36 Correct 8 ms 17492 KB Output is correct
37 Correct 20 ms 31556 KB Output is correct
38 Correct 22 ms 32844 KB Output is correct
39 Correct 17 ms 32436 KB Output is correct
40 Correct 18 ms 32556 KB Output is correct
41 Correct 19 ms 32852 KB Output is correct
42 Correct 16 ms 32348 KB Output is correct
43 Correct 16 ms 32356 KB Output is correct
44 Correct 16 ms 32340 KB Output is correct
45 Correct 44 ms 32712 KB Output is correct
46 Correct 35 ms 32724 KB Output is correct
47 Correct 83 ms 195276 KB Output is correct
48 Runtime error 102 ms 262144 KB Execution killed with signal 9
49 Halted 0 ms 0 KB -