oj.uz

Submission #998790

# Submission time Handle Problem Language Result Execution time Memory
998790 2024-06-14T16:58:27 Z assanali Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 872 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]);
        }
    }
    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(!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;
    }
    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 2648 KB Output is correct
2 Correct 1 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 0 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 0 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 0 ms 2652 KB Output is correct
6 Correct 1 ms 2648 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 2648 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 4 ms 10588 KB Output is correct
12 Correct 7 ms 11608 KB Output is correct
13 Correct 7 ms 15196 KB Output is correct
14 Correct 4 ms 13404 KB Output is correct
15 Correct 3 ms 14172 KB Output is correct

Subtask #3
14.0 / 14.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 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
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 4696 KB Output is correct
11 Correct 3 ms 14172 KB Output is correct
12 Correct 6 ms 15196 KB Output is correct
13 Correct 7 ms 16240 KB Output is correct
14 Correct 3 ms 14176 KB Output is correct
15 Correct 3 ms 15196 KB Output is correct
16 Correct 0 ms 2652 KB Output is correct
17 Correct 5 ms 13588 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 28 ms 33116 KB Output is correct
21 Correct 1 ms 8796 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 2 ms 8028 KB Output is correct
24 Correct 4 ms 14684 KB Output is correct
25 Correct 4 ms 15964 KB Output is correct
26 Correct 10 ms 17852 KB Output is correct
27 Correct 10 ms 17500 KB Output is correct
28 Correct 3 ms 16732 KB Output is correct
29 Correct 1 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 6808 KB Output is correct
33 Correct 4 ms 12380 KB Output is correct
34 Correct 5 ms 12380 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 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
8 Correct 0 ms 2652 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 4696 KB Output is correct
11 Correct 4 ms 12420 KB Output is correct
12 Correct 6 ms 16220 KB Output is correct
13 Correct 7 ms 16220 KB Output is correct
14 Correct 3 ms 16284 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 5 ms 12512 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 6732 KB Output is correct
20 Correct 32 ms 33108 KB Output is correct
21 Correct 1 ms 4700 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 5 ms 14940 KB Output is correct
25 Correct 5 ms 15192 KB Output is correct
26 Correct 14 ms 17884 KB Output is correct
27 Correct 12 ms 17400 KB Output is correct
28 Correct 3 ms 15964 KB Output is correct
29 Correct 1 ms 7004 KB Output is correct
30 Correct 1 ms 4700 KB Output is correct
31 Correct 1 ms 5212 KB Output is correct
32 Correct 1 ms 4956 KB Output is correct
33 Correct 4 ms 10332 KB Output is correct
34 Correct 4 ms 11356 KB Output is correct
35 Correct 76 ms 159796 KB Output is correct
36 Correct 11 ms 29276 KB Output is correct
37 Correct 77 ms 156368 KB Output is correct
38 Correct 107 ms 211024 KB Output is correct
39 Correct 105 ms 209748 KB Output is correct
40 Correct 101 ms 211028 KB Output is correct
41 Correct 100 ms 211280 KB Output is correct
42 Correct 757 ms 251820 KB Output is correct
43 Correct 872 ms 244564 KB Output is correct
44 Runtime error 574 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 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 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 1 ms 2648 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Correct 5 ms 15196 KB Output is correct
13 Correct 7 ms 15196 KB Output is correct
14 Correct 3 ms 14172 KB Output is correct
15 Correct 3 ms 15196 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 3 ms 15452 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 29 ms 33116 KB Output is correct
21 Correct 1 ms 8796 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 1 ms 8952 KB Output is correct
24 Correct 4 ms 14172 KB Output is correct
25 Correct 4 ms 14172 KB Output is correct
26 Correct 12 ms 17788 KB Output is correct
27 Correct 13 ms 17360 KB Output is correct
28 Correct 4 ms 15196 KB Output is correct
29 Correct 1 ms 7004 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 6 ms 12380 KB Output is correct
34 Correct 4 ms 12380 KB Output is correct
35 Correct 77 ms 160308 KB Output is correct
36 Correct 11 ms 31324 KB Output is correct
37 Correct 73 ms 156356 KB Output is correct
38 Correct 104 ms 211220 KB Output is correct
39 Correct 100 ms 210512 KB Output is correct
40 Correct 103 ms 211284 KB Output is correct
41 Correct 101 ms 211540 KB Output is correct
42 Correct 754 ms 251984 KB Output is correct
43 Correct 752 ms 244444 KB Output is correct
44 Runtime error 551 ms 262144 KB Execution killed with signal 9
45 Halted 0 ms 0 KB -