oj.uz

Submission #998793

# Submission time Handle Problem Language Result Execution time Memory
998793 2024-06-14T16:59:41 Z assanali Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 841 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[30001][2001], d[30010];
vector <ll> v[N];
vector <ll> road[2010];
bool used[30001];
// 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);
}
used[0]=true;
for(ll j = 0; j< 1; j++) {
    cost[j][b[j]]=0;
    v[j].pb(b[j]);
    for(ll i = 1; b[j] + i * p[j] < n; i += 1) {
        if(!road[b[j] + i * p[j]].empty()) {
            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) {
        if(!road[b[j] - i * p[j]].empty()) {
            cost[j][b[j] - i * p[j]] = i;
            v[j].pb(b[j] - i * p[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;}
    if(!used[ver]) {
        ll j = ver;
        cost[j][b[j]]=0;
        v[j].pb(b[j]);
        for(ll i = 1; b[j] + i * p[j] < n; i += 1) {
            if(!road[b[j] + i * p[j]].empty()) {
                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) {
            if(!road[b[j] - i * p[j]].empty()) {
                cost[j][b[j] - i * p[j]] = i;
                v[j].pb(b[j] - i * p[j]);
            }
        }
        used[ver] = true;
    }
    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 1 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 2652 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 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 0 ms 2652 KB Output is correct
7 Correct 0 ms 2652 KB Output is correct
8 Correct 0 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 12380 KB Output is correct
12 Correct 9 ms 13460 KB Output is correct
13 Correct 7 ms 14424 KB Output is correct
14 Correct 4 ms 14424 KB Output is correct
15 Correct 4 ms 12376 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 1 ms 2652 KB Output is correct
3 Correct 1 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 2 ms 4700 KB Output is correct
11 Correct 6 ms 9772 KB Output is correct
12 Correct 7 ms 10076 KB Output is correct
13 Correct 8 ms 11100 KB Output is correct
14 Correct 5 ms 9724 KB Output is correct
15 Correct 7 ms 10332 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 9 ms 12124 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 32 ms 32848 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 3 ms 6236 KB Output is correct
24 Correct 5 ms 13148 KB Output is correct
25 Correct 5 ms 12892 KB Output is correct
26 Correct 14 ms 17752 KB Output is correct
27 Correct 23 ms 16988 KB Output is correct
28 Correct 8 ms 14424 KB Output is correct
29 Correct 2 ms 4956 KB Output is correct
30 Correct 1 ms 1992 KB Output is correct
31 Correct 1 ms 4188 KB Output is correct
32 Correct 1 ms 6748 KB Output is correct
33 Correct 4 ms 14172 KB Output is correct
34 Correct 4 ms 15196 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 1 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 1 ms 2652 KB Output is correct
7 Correct 0 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 4 ms 12380 KB Output is correct
12 Correct 6 ms 12636 KB Output is correct
13 Correct 7 ms 13404 KB Output is correct
14 Correct 4 ms 13404 KB Output is correct
15 Correct 4 ms 14168 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 4 ms 13916 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 38 ms 32960 KB Output is correct
21 Correct 1 ms 6748 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 5 ms 14212 KB Output is correct
25 Correct 4 ms 14620 KB Output is correct
26 Correct 12 ms 17784 KB Output is correct
27 Correct 12 ms 17500 KB Output is correct
28 Correct 5 ms 16732 KB Output is correct
29 Correct 2 ms 8796 KB Output is correct
30 Correct 1 ms 4700 KB Output is correct
31 Correct 1 ms 6748 KB Output is correct
32 Correct 2 ms 6748 KB Output is correct
33 Correct 4 ms 13308 KB Output is correct
34 Correct 5 ms 15192 KB Output is correct
35 Correct 79 ms 161704 KB Output is correct
36 Correct 11 ms 32088 KB Output is correct
37 Correct 84 ms 156400 KB Output is correct
38 Correct 117 ms 211360 KB Output is correct
39 Correct 123 ms 210172 KB Output is correct
40 Correct 105 ms 211600 KB Output is correct
41 Correct 104 ms 211552 KB Output is correct
42 Correct 795 ms 252064 KB Output is correct
43 Correct 788 ms 244564 KB Output is correct
44 Runtime error 548 ms 262144 KB Execution killed with signal 9
45 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 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 0 ms 2652 KB Output is correct
7 Correct 0 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 3 ms 13404 KB Output is correct
12 Correct 5 ms 15196 KB Output is correct
13 Correct 7 ms 16220 KB Output is correct
14 Correct 3 ms 16220 KB Output is correct
15 Correct 3 ms 16220 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 4 ms 13916 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 30 ms 33128 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 5 ms 13660 KB Output is correct
25 Correct 4 ms 15196 KB Output is correct
26 Correct 12 ms 17752 KB Output is correct
27 Correct 11 ms 17500 KB Output is correct
28 Correct 4 ms 15960 KB Output is correct
29 Correct 2 ms 8796 KB Output is correct
30 Correct 1 ms 4700 KB Output is correct
31 Correct 1 ms 6748 KB Output is correct
32 Correct 1 ms 6748 KB Output is correct
33 Correct 3 ms 14172 KB Output is correct
34 Correct 4 ms 14340 KB Output is correct
35 Correct 75 ms 161240 KB Output is correct
36 Correct 12 ms 29272 KB Output is correct
37 Correct 72 ms 156244 KB Output is correct
38 Correct 107 ms 211028 KB Output is correct
39 Correct 98 ms 209796 KB Output is correct
40 Correct 103 ms 211028 KB Output is correct
41 Correct 102 ms 211164 KB Output is correct
42 Correct 841 ms 251988 KB Output is correct
43 Correct 780 ms 244564 KB Output is correct
44 Runtime error 571 ms 262144 KB Execution killed with signal 9
45 Halted 0 ms 0 KB -