oj.uz

Submission #544566

# Submission time Handle Problem Language Result Execution time Memory
544566 2022-04-02T11:16:34 Z SavicS Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 98376 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];

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 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7348 KB Output is correct
5 Correct 4 ms 7388 KB Output is correct
6 Correct 4 ms 7328 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 7 ms 7336 KB Output is correct
4 Correct 5 ms 7304 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7328 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 6 ms 7524 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 5 ms 7492 KB Output is correct
14 Correct 5 ms 7636 KB Output is correct
15 Correct 6 ms 7636 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7380 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 7 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7388 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7636 KB Output is correct
15 Correct 5 ms 7548 KB Output is correct
16 Correct 4 ms 7508 KB Output is correct
17 Correct 7 ms 7848 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 5 ms 7508 KB Output is correct
20 Correct 5 ms 7636 KB Output is correct
21 Correct 4 ms 7380 KB Output is correct
22 Correct 7 ms 7508 KB Output is correct
23 Correct 5 ms 7508 KB Output is correct
24 Correct 6 ms 7764 KB Output is correct
25 Correct 6 ms 7636 KB Output is correct
26 Correct 6 ms 7768 KB Output is correct
27 Correct 6 ms 7656 KB Output is correct
28 Correct 13 ms 8156 KB Output is correct
29 Correct 29 ms 10700 KB Output is correct
30 Correct 7 ms 8404 KB Output is correct
31 Correct 11 ms 9184 KB Output is correct
32 Correct 8 ms 8660 KB Output is correct
33 Correct 37 ms 14056 KB Output is correct
34 Correct 38 ms 14036 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7264 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7264 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7324 KB Output is correct
9 Correct 8 ms 7304 KB Output is correct
10 Correct 9 ms 7448 KB Output is correct
11 Correct 7 ms 7508 KB Output is correct
12 Correct 10 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 6 ms 7664 KB Output is correct
15 Correct 5 ms 7636 KB Output is correct
16 Correct 11 ms 7508 KB Output is correct
17 Correct 7 ms 7892 KB Output is correct
18 Correct 30 ms 7604 KB Output is correct
19 Correct 5 ms 7508 KB Output is correct
20 Correct 12 ms 7636 KB Output is correct
21 Correct 4 ms 7380 KB Output is correct
22 Correct 11 ms 7508 KB Output is correct
23 Correct 6 ms 7508 KB Output is correct
24 Correct 7 ms 7764 KB Output is correct
25 Correct 6 ms 7636 KB Output is correct
26 Correct 6 ms 7764 KB Output is correct
27 Correct 5 ms 7652 KB Output is correct
28 Correct 8 ms 8040 KB Output is correct
29 Correct 20 ms 10708 KB Output is correct
30 Correct 7 ms 8404 KB Output is correct
31 Correct 11 ms 9172 KB Output is correct
32 Correct 8 ms 8672 KB Output is correct
33 Correct 37 ms 14028 KB Output is correct
34 Correct 38 ms 14004 KB Output is correct
35 Correct 29 ms 10908 KB Output is correct
36 Correct 7 ms 7948 KB Output is correct
37 Correct 57 ms 13944 KB Output is correct
38 Correct 50 ms 13132 KB Output is correct
39 Correct 65 ms 13216 KB Output is correct
40 Correct 66 ms 13100 KB Output is correct
41 Correct 49 ms 13168 KB Output is correct
42 Correct 11 ms 8800 KB Output is correct
43 Correct 10 ms 8668 KB Output is correct
44 Correct 11 ms 8656 KB Output is correct
45 Correct 290 ms 33208 KB Output is correct
46 Correct 297 ms 33244 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 6 ms 7380 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 8 ms 7508 KB Output is correct
12 Correct 7 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7600 KB Output is correct
15 Correct 9 ms 7636 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 7 ms 7916 KB Output is correct
18 Correct 5 ms 7580 KB Output is correct
19 Correct 5 ms 7508 KB Output is correct
20 Correct 11 ms 7636 KB Output is correct
21 Correct 5 ms 7352 KB Output is correct
22 Correct 4 ms 7492 KB Output is correct
23 Correct 5 ms 7508 KB Output is correct
24 Correct 6 ms 7764 KB Output is correct
25 Correct 6 ms 7636 KB Output is correct
26 Correct 6 ms 7764 KB Output is correct
27 Correct 6 ms 7660 KB Output is correct
28 Correct 7 ms 8104 KB Output is correct
29 Correct 18 ms 10828 KB Output is correct
30 Correct 7 ms 8420 KB Output is correct
31 Correct 10 ms 9252 KB Output is correct
32 Correct 8 ms 8668 KB Output is correct
33 Correct 61 ms 14052 KB Output is correct
34 Correct 37 ms 13968 KB Output is correct
35 Correct 31 ms 10900 KB Output is correct
36 Correct 8 ms 7892 KB Output is correct
37 Correct 64 ms 13920 KB Output is correct
38 Correct 50 ms 13104 KB Output is correct
39 Correct 48 ms 13260 KB Output is correct
40 Correct 49 ms 13072 KB Output is correct
41 Correct 49 ms 13152 KB Output is correct
42 Correct 12 ms 8784 KB Output is correct
43 Correct 10 ms 8668 KB Output is correct
44 Correct 10 ms 8660 KB Output is correct
45 Correct 267 ms 33208 KB Output is correct
46 Correct 308 ms 33284 KB Output is correct
47 Correct 414 ms 35560 KB Output is correct
48 Correct 67 ms 15484 KB Output is correct
49 Correct 42 ms 12124 KB Output is correct
50 Correct 45 ms 12360 KB Output is correct
51 Correct 128 ms 19420 KB Output is correct
52 Correct 120 ms 20680 KB Output is correct
53 Correct 27 ms 11732 KB Output is correct
54 Correct 8 ms 9052 KB Output is correct
55 Correct 12 ms 10448 KB Output is correct
56 Correct 23 ms 11544 KB Output is correct
57 Correct 253 ms 33488 KB Output is correct
58 Correct 24 ms 11580 KB Output is correct
59 Correct 25 ms 13640 KB Output is correct
60 Correct 56 ms 15408 KB Output is correct
61 Correct 23 ms 12488 KB Output is correct
62 Correct 157 ms 23240 KB Output is correct
63 Execution timed out 1085 ms 98376 KB Time limit exceeded
64 Halted 0 ms 0 KB -