oj.uz

Submission #998772

# Submission time Handle Problem Language Result Execution time Memory
998772 2024-06-14T16:41:53 Z assanali Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 413 ms 262144 KB 
/*

author: CRISTIANO RONALDO


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
can do: find_by_order, order_of_key

__builtin_clz(x): the number of zeros at the beginning of the number
__builtin_ctz(x): the number of zeros at the end of the number
__builtin_popcount(x): the number of ones in the number
__builtin_parity(x): the parity (even or odd) of the number of ones

mt19937 rng(15);
mt19937 bruh(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
*/
#include <bits/stdc++.h>
#define ll int
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define pb push_back
#define ull unsigned long long
#define ld long double
#define lv v+v
#define rv v+v+1
#define files freopen("aa.txt", "r", stdin), freopen("aa.txt", "w", stdout)
#define pll pair <long long, long long>
#define pii pair <int, int>
using namespace std;
long long mod = 1e9 + 7;
const ll N = 3e4 + 10;
const ll M = 2e3 + 10;
const ll P = 337ll;
const ld EPS = 1e-7;
const ll block = 325;
const ll inf = 2e9;
ll n,m,b[N],p[N],cost[30010][2010], d[30010];
vector <ll> v[N];
vector <ll> road[2010];
// v[j] - куда может прыгнуть собака j
// cost[j][u] - цена прыжка собаки j в точку u
// road[j] - Какие собаки живут в точке j
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
for(ll i = 0; i<m; i++) {
    cin>>b[i]>>p[i];
    d[i] = inf;
    road[b[i]].pb(i);
}
for(ll j = 0; j< m; j++) {
    cost[j][b[j]]=0;
    v[j].pb(b[j]);
    for(ll i = 1; b[j] + i * p[j] < n; i += 1) {
        cost[j][b[j] + i * p[j]] = i;
        v[j].pb(b[j] + i * p[j]);
    }
    for(ll i = 1; b[j] - i * p[j] >= 0; i += 1) {
        cost[j][b[j] - i * p[j]] = i;
        v[j].pb(b[j] - i * p[j]);
    }
    sort(all(v[j]));
}
set <pii> q;
q.insert({0,0});
d[0] = 0;
while(!q.empty()) {
    ll ver = (*q.begin()).S;    ll ttt = (*q.begin()).F; q.erase(q.begin());
    if(ttt > d[ver]) {continue;}
    for(auto u : v[ver]) {
        for(auto j : road[u]) {
            if(d[j] > d[ver] + cost[ver][u]) {
                d[j] = d[ver] + cost[ver][u];
                q.insert({d[j], j});
            }
        }
    }
}
cout<<(d[1] == inf ? -1 : d[1]);
return 0;
}
// equal, min, max, 1, random, build
/*

*/

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 0 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 0 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 4 ms 14232 KB Output is correct
12 Correct 8 ms 13684 KB Output is correct
13 Correct 8 ms 15452 KB Output is correct
14 Correct 4 ms 12564 KB Output is correct
15 Correct 4 ms 13404 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 0 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 0 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 3 ms 14428 KB Output is correct
12 Correct 7 ms 15488 KB Output is correct
13 Correct 7 ms 16220 KB Output is correct
14 Correct 3 ms 15452 KB Output is correct
15 Correct 3 ms 14428 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 4 ms 14924 KB Output is correct
18 Correct 1 ms 10844 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 163 ms 33148 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 1 ms 7256 KB Output is correct
23 Correct 2 ms 8796 KB Output is correct
24 Correct 6 ms 14940 KB Output is correct
25 Correct 6 ms 15624 KB Output is correct
26 Correct 56 ms 31568 KB Output is correct
27 Correct 65 ms 30796 KB Output is correct
28 Correct 4 ms 15960 KB Output is correct
29 Correct 2 ms 9052 KB Output is correct
30 Correct 1 ms 4700 KB Output is correct
31 Correct 2 ms 7000 KB Output is correct
32 Correct 1 ms 6744 KB Output is correct
33 Correct 5 ms 18012 KB Output is correct
34 Correct 8 ms 18048 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 0 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 0 ms 2652 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 4 ms 13404 KB Output is correct
12 Correct 7 ms 14388 KB Output is correct
13 Correct 8 ms 14412 KB Output is correct
14 Correct 4 ms 12636 KB Output is correct
15 Correct 4 ms 13404 KB Output is correct
16 Correct 1 ms 7260 KB Output is correct
17 Correct 4 ms 14172 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 136 ms 33108 KB Output is correct
21 Correct 2 ms 10840 KB Output is correct
22 Correct 1 ms 8792 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 3 ms 17244 KB Output is correct
25 Correct 3 ms 19292 KB Output is correct
26 Correct 48 ms 31680 KB Output is correct
27 Correct 66 ms 32784 KB Output is correct
28 Correct 3 ms 17244 KB Output is correct
29 Correct 2 ms 9048 KB Output is correct
30 Correct 1 ms 4700 KB Output is correct
31 Correct 2 ms 7004 KB Output is correct
32 Correct 1 ms 6748 KB Output is correct
33 Correct 7 ms 18012 KB Output is correct
34 Correct 7 ms 18008 KB Output is correct
35 Correct 80 ms 161616 KB Output is correct
36 Correct 13 ms 28760 KB Output is correct
37 Correct 81 ms 157780 KB Output is correct
38 Correct 110 ms 212804 KB Output is correct
39 Correct 108 ms 212308 KB Output is correct
40 Correct 104 ms 213328 KB Output is correct
41 Correct 111 ms 213180 KB Output is correct
42 Runtime error 390 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 0 ms 2652 KB Output is correct
4 Correct 0 ms 2652 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 5 ms 13360 KB Output is correct
12 Correct 8 ms 15452 KB Output is correct
13 Correct 7 ms 15472 KB Output is correct
14 Correct 4 ms 13404 KB Output is correct
15 Correct 4 ms 13404 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 4 ms 14428 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 133 ms 33144 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 1 ms 7004 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 5 ms 15136 KB Output is correct
25 Correct 5 ms 15068 KB Output is correct
26 Correct 54 ms 31572 KB Output is correct
27 Correct 66 ms 30800 KB Output is correct
28 Correct 5 ms 15448 KB Output is correct
29 Correct 2 ms 9052 KB Output is correct
30 Correct 1 ms 4700 KB Output is correct
31 Correct 1 ms 7004 KB Output is correct
32 Correct 2 ms 6748 KB Output is correct
33 Correct 7 ms 18012 KB Output is correct
34 Correct 7 ms 17980 KB Output is correct
35 Correct 88 ms 160016 KB Output is correct
36 Correct 12 ms 26716 KB Output is correct
37 Correct 108 ms 157888 KB Output is correct
38 Correct 112 ms 211896 KB Output is correct
39 Correct 106 ms 210520 KB Output is correct
40 Correct 105 ms 213588 KB Output is correct
41 Correct 106 ms 213108 KB Output is correct
42 Runtime error 413 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -