oj.uz

Submission #544568

# Submission time Handle Problem Language Result Execution time Memory
544568 2022-04-02T11:17:53 Z SavicS Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 105372 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
 
#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for (auto& a : x)
 
#define sz(a) (int)(a).size()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 100005; 

int n, m;
int B[mxN];
int P[mxN];

vector<pii> g[mxN];
int dist[mxN];

unordered_map<int,int> mp[mxN];

int id[mxN];
bool cmp(int s1, int s2){
    return B[s1] < B[s2];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> m >> n;
    ff(i,0,n - 1)cin >> B[i] >> P[i];

    int S = B[0];
    int T = B[1];

    ff(i,0,n - 1)id[i] = i;
    sort(id, id + n, cmp);

    ff(i,0,n - 1){
        int pos = B[id[i]] + P[id[i]], cost = 1;
        while(pos < m){
            g[B[id[i]]].pb({pos, cost}); cost += 1;
            if(mp[pos].count(P[id[i]]) == 1)break;
            mp[pos][P[id[i]]] = 1;
            pos += P[id[i]];
        }
    }    

    ff(i,0,m - 1)mp[i].clear();

    ff(i,0,n - 1){
        int pos = B[id[i]] - P[id[i]], cost = 1;
        while(pos >= 0){
            g[B[id[i]]].pb({pos, cost}); cost += 1;
            if(mp[pos].count(P[id[i]]) == 1)break;
            mp[pos][P[id[i]]] = 1;
            pos -= P[id[i]];
        }
    }

    ff(i,0,m - 1)dist[i] = inf;
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    pq.push({dist[S] = 0, S});
    while(sz(pq)){
        pii v = pq.top(); pq.pop();
        if(dist[v.se] < v.fi)continue;
        for(auto c : g[v.se]){
            int u = c.fi;
            int w = c.se;
            if(dist[u] > v.fi + w){
                pq.push({dist[u] = v.fi + w, u});
            }
        }
    }

    cout << (dist[T] == inf ? -1 : dist[T]) << '\n';

    return 0;
}
/*

6 4
4 5
0 3
5 1
4 1

18 10
1 2
0 12
1 17
4 1
3 1
5 13
14 7
5 16
15 6
9 5

51 9
9 1
45 2
42 38
17 9
39 44
35 1
22 41
43 35
3 36
 
22 19
10 10
13 5
1 1
17 17
2 3
3 9
20 22
18 1
3 5
11 16
7 16
2 22
20 4
11 19
7 1
16 1
11 14
8 9
3 18

5 3 
0 2 
1 1 
4 1
 
// probati bojenje sahovski
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 5 ms 8276 KB Output is correct
12 Correct 5 ms 8148 KB Output is correct
13 Correct 5 ms 8276 KB Output is correct
14 Correct 6 ms 8396 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 5 ms 8164 KB Output is correct
5 Correct 5 ms 8112 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 5 ms 8140 KB Output is correct
11 Correct 5 ms 8276 KB Output is correct
12 Correct 5 ms 8256 KB Output is correct
13 Correct 5 ms 8276 KB Output is correct
14 Correct 5 ms 8428 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 5 ms 8276 KB Output is correct
17 Correct 7 ms 8660 KB Output is correct
18 Correct 7 ms 8532 KB Output is correct
19 Correct 5 ms 8404 KB Output is correct
20 Correct 6 ms 8660 KB Output is correct
21 Correct 5 ms 8276 KB Output is correct
22 Correct 6 ms 8404 KB Output is correct
23 Correct 6 ms 8452 KB Output is correct
24 Correct 7 ms 8660 KB Output is correct
25 Correct 6 ms 8660 KB Output is correct
26 Correct 6 ms 8656 KB Output is correct
27 Correct 6 ms 8532 KB Output is correct
28 Correct 7 ms 8916 KB Output is correct
29 Correct 16 ms 11744 KB Output is correct
30 Correct 7 ms 9172 KB Output is correct
31 Correct 10 ms 10068 KB Output is correct
32 Correct 8 ms 9416 KB Output is correct
33 Correct 33 ms 14800 KB Output is correct
34 Correct 33 ms 14892 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 5 ms 8104 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 5 ms 8148 KB Output is correct
7 Correct 7 ms 8176 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 7 ms 8120 KB Output is correct
11 Correct 5 ms 8276 KB Output is correct
12 Correct 5 ms 8148 KB Output is correct
13 Correct 5 ms 8276 KB Output is correct
14 Correct 5 ms 8404 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 5 ms 8276 KB Output is correct
17 Correct 8 ms 8660 KB Output is correct
18 Correct 6 ms 8532 KB Output is correct
19 Correct 5 ms 8444 KB Output is correct
20 Correct 5 ms 8660 KB Output is correct
21 Correct 7 ms 8148 KB Output is correct
22 Correct 7 ms 8512 KB Output is correct
23 Correct 5 ms 8404 KB Output is correct
24 Correct 8 ms 8660 KB Output is correct
25 Correct 6 ms 8660 KB Output is correct
26 Correct 6 ms 8764 KB Output is correct
27 Correct 9 ms 8692 KB Output is correct
28 Correct 7 ms 8916 KB Output is correct
29 Correct 22 ms 11720 KB Output is correct
30 Correct 7 ms 9172 KB Output is correct
31 Correct 11 ms 10024 KB Output is correct
32 Correct 8 ms 9428 KB Output is correct
33 Correct 30 ms 14880 KB Output is correct
34 Correct 40 ms 14980 KB Output is correct
35 Correct 28 ms 11592 KB Output is correct
36 Correct 10 ms 8668 KB Output is correct
37 Correct 58 ms 14808 KB Output is correct
38 Correct 43 ms 13800 KB Output is correct
39 Correct 41 ms 14036 KB Output is correct
40 Correct 45 ms 13952 KB Output is correct
41 Correct 45 ms 13944 KB Output is correct
42 Correct 16 ms 9488 KB Output is correct
43 Correct 12 ms 9468 KB Output is correct
44 Correct 13 ms 9488 KB Output is correct
45 Correct 182 ms 30724 KB Output is correct
46 Correct 211 ms 30672 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 6 ms 8148 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 6 ms 8120 KB Output is correct
9 Correct 6 ms 8076 KB Output is correct
10 Correct 6 ms 8148 KB Output is correct
11 Correct 6 ms 8276 KB Output is correct
12 Correct 7 ms 8272 KB Output is correct
13 Correct 6 ms 8280 KB Output is correct
14 Correct 6 ms 8404 KB Output is correct
15 Correct 8 ms 8404 KB Output is correct
16 Correct 5 ms 8276 KB Output is correct
17 Correct 7 ms 8660 KB Output is correct
18 Correct 6 ms 8548 KB Output is correct
19 Correct 6 ms 8392 KB Output is correct
20 Correct 8 ms 8692 KB Output is correct
21 Correct 5 ms 8148 KB Output is correct
22 Correct 6 ms 8404 KB Output is correct
23 Correct 6 ms 8404 KB Output is correct
24 Correct 8 ms 8660 KB Output is correct
25 Correct 8 ms 8660 KB Output is correct
26 Correct 7 ms 8672 KB Output is correct
27 Correct 7 ms 8532 KB Output is correct
28 Correct 8 ms 8916 KB Output is correct
29 Correct 21 ms 11732 KB Output is correct
30 Correct 10 ms 9092 KB Output is correct
31 Correct 12 ms 10040 KB Output is correct
32 Correct 10 ms 9424 KB Output is correct
33 Correct 41 ms 14860 KB Output is correct
34 Correct 43 ms 14912 KB Output is correct
35 Correct 29 ms 11600 KB Output is correct
36 Correct 8 ms 8660 KB Output is correct
37 Correct 52 ms 14732 KB Output is correct
38 Correct 46 ms 13892 KB Output is correct
39 Correct 40 ms 14012 KB Output is correct
40 Correct 41 ms 13948 KB Output is correct
41 Correct 44 ms 13904 KB Output is correct
42 Correct 11 ms 9424 KB Output is correct
43 Correct 12 ms 9424 KB Output is correct
44 Correct 10 ms 9424 KB Output is correct
45 Correct 185 ms 30700 KB Output is correct
46 Correct 157 ms 30712 KB Output is correct
47 Correct 466 ms 36448 KB Output is correct
48 Correct 63 ms 16952 KB Output is correct
49 Correct 39 ms 14548 KB Output is correct
50 Correct 44 ms 14980 KB Output is correct
51 Correct 142 ms 20916 KB Output is correct
52 Correct 117 ms 22156 KB Output is correct
53 Correct 53 ms 14804 KB Output is correct
54 Correct 15 ms 12884 KB Output is correct
55 Correct 26 ms 13796 KB Output is correct
56 Correct 28 ms 15736 KB Output is correct
57 Correct 268 ms 35364 KB Output is correct
58 Correct 23 ms 15048 KB Output is correct
59 Correct 44 ms 16212 KB Output is correct
60 Correct 61 ms 17544 KB Output is correct
61 Correct 45 ms 15404 KB Output is correct
62 Correct 158 ms 23976 KB Output is correct
63 Execution timed out 1085 ms 105372 KB Time limit exceeded
64 Halted 0 ms 0 KB -