oj.uz

Submission #998771

# Submission time Handle Problem Language Result Execution time Memory
998771 2024-06-14T16:40:41 Z assanali Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 152 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 long long
#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 = 2e18;
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 <pll> 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 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 1 ms 2692 KB Output is correct
7 Correct 1 ms 2664 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2648 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 4188 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 9 ms 13916 KB Output is correct
13 Correct 9 ms 15448 KB Output is correct
14 Correct 5 ms 16008 KB Output is correct
15 Correct 5 ms 17608 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 2652 KB Output is correct
6 Correct 0 ms 2688 KB Output is correct
7 Correct 0 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 7004 KB Output is correct
11 Correct 5 ms 14680 KB Output is correct
12 Correct 9 ms 16728 KB Output is correct
13 Correct 10 ms 16988 KB Output is correct
14 Correct 5 ms 14472 KB Output is correct
15 Correct 4 ms 14684 KB Output is correct
16 Correct 2 ms 12168 KB Output is correct
17 Correct 7 ms 18012 KB Output is correct
18 Correct 3 ms 14428 KB Output is correct
19 Correct 2 ms 10840 KB Output is correct
20 Correct 146 ms 65024 KB Output is correct
21 Correct 2 ms 13404 KB Output is correct
22 Correct 2 ms 11100 KB Output is correct
23 Correct 3 ms 14172 KB Output is correct
24 Correct 7 ms 23488 KB Output is correct
25 Correct 7 ms 20536 KB Output is correct
26 Correct 64 ms 62036 KB Output is correct
27 Correct 76 ms 60208 KB Output is correct
28 Correct 7 ms 24668 KB Output is correct
29 Correct 4 ms 13916 KB Output is correct
30 Correct 1 ms 4956 KB Output is correct
31 Correct 3 ms 11100 KB Output is correct
32 Correct 3 ms 9308 KB Output is correct
33 Correct 14 ms 34652 KB Output is correct
34 Correct 14 ms 34608 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 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 0 ms 2652 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 5 ms 20316 KB Output is correct
12 Correct 9 ms 21084 KB Output is correct
13 Correct 9 ms 21248 KB Output is correct
14 Correct 5 ms 19036 KB Output is correct
15 Correct 5 ms 20572 KB Output is correct
16 Correct 2 ms 13596 KB Output is correct
17 Correct 7 ms 21852 KB Output is correct
18 Correct 2 ms 16084 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 141 ms 64980 KB Output is correct
21 Correct 2 ms 19292 KB Output is correct
22 Correct 2 ms 12892 KB Output is correct
23 Correct 3 ms 14172 KB Output is correct
24 Correct 7 ms 23388 KB Output is correct
25 Correct 5 ms 26172 KB Output is correct
26 Correct 60 ms 62028 KB Output is correct
27 Correct 78 ms 60332 KB Output is correct
28 Correct 7 ms 27996 KB Output is correct
29 Correct 3 ms 15708 KB Output is correct
30 Correct 1 ms 4952 KB Output is correct
31 Correct 2 ms 11100 KB Output is correct
32 Correct 2 ms 11100 KB Output is correct
33 Correct 11 ms 34660 KB Output is correct
34 Correct 11 ms 34652 KB Output is correct
35 Correct 97 ms 213184 KB Output is correct
36 Correct 14 ms 44124 KB Output is correct
37 Runtime error 88 ms 262144 KB Execution killed with signal 9
38 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 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 2908 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 8796 KB Output is correct
11 Correct 5 ms 18776 KB Output is correct
12 Correct 9 ms 21084 KB Output is correct
13 Correct 9 ms 22456 KB Output is correct
14 Correct 4 ms 20572 KB Output is correct
15 Correct 5 ms 20572 KB Output is correct
16 Correct 2 ms 13404 KB Output is correct
17 Correct 7 ms 21852 KB Output is correct
18 Correct 2 ms 15964 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 152 ms 65016 KB Output is correct
21 Correct 3 ms 14936 KB Output is correct
22 Correct 2 ms 12892 KB Output is correct
23 Correct 3 ms 14940 KB Output is correct
24 Correct 6 ms 25044 KB Output is correct
25 Correct 6 ms 22876 KB Output is correct
26 Correct 65 ms 62072 KB Output is correct
27 Correct 75 ms 60244 KB Output is correct
28 Correct 7 ms 26200 KB Output is correct
29 Correct 3 ms 13916 KB Output is correct
30 Correct 1 ms 4956 KB Output is correct
31 Correct 2 ms 11100 KB Output is correct
32 Correct 2 ms 11228 KB Output is correct
33 Correct 11 ms 34652 KB Output is correct
34 Correct 12 ms 34652 KB Output is correct
35 Correct 103 ms 213292 KB Output is correct
36 Correct 15 ms 40536 KB Output is correct
37 Runtime error 92 ms 262144 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -