답안 #998879

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998879	2024-06-14T18:55:56 Z	assanali	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	608 ms	16724 KB

skyscraper

/*

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], d[30010];
vector <ll> road[30010];
// 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];
    road[b[i]].pb(p[i]);
}
for(ll i = 0; i<n; i++) {
    d[i] = inf;
}
set <pll> q;
q.insert({0,b[0]});
d[b[0]] = 0;
ll ver, ttt, j,jj;
while(!q.empty()) {
    ver = (*q.begin()).S;    ttt = (*q.begin()).F; q.erase(q.begin());
    if(ttt > d[ver]) {continue;}
    j = ver;
    for(auto to : road[j]) {
        for(ll i = 1; j + i * to < n; i += 1) {
            jj = j + i * to;
            if(d[jj] > d[ver] + i) {
                d[jj] = d[ver] + i;
                q.insert({d[jj], jj});
            }
        }
        for(ll i = 0; j - i * to >= 0; i += 1) {
            jj = j - i * to;
            if(d[jj] > d[ver] + i) {
                d[jj] = d[ver] + i;
                q.insert({d[jj], jj});
            }
        }
    }
}
cout<<(d[b[1]] == inf ? -1 : d[b[1]]);
return 0;
}
// equal, min, max, 1, random, build
/*

*/

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1116 KB	Output is correct
2	Correct	0 ms	972 KB	Output is correct
3	Correct	1 ms	1116 KB	Output is correct
4	Correct	0 ms	1116 KB	Output is correct
5	Correct	0 ms	1116 KB	Output is correct
6	Correct	0 ms	1116 KB	Output is correct
7	Correct	0 ms	1116 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1112 KB	Output is correct
2	Correct	1 ms	1168 KB	Output is correct
3	Correct	1 ms	1116 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	1 ms	1116 KB	Output is correct
6	Correct	1 ms	1116 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	0 ms	1116 KB	Output is correct
10	Correct	1 ms	1116 KB	Output is correct
11	Correct	1 ms	1116 KB	Output is correct
12	Correct	1 ms	1116 KB	Output is correct
13	Correct	1 ms	1116 KB	Output is correct
14	Correct	1 ms	1116 KB	Output is correct
15	Correct	1 ms	1116 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1116 KB	Output is correct
2	Correct	0 ms	1116 KB	Output is correct
3	Correct	1 ms	1368 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	1 ms	1112 KB	Output is correct
6	Correct	0 ms	1116 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	1 ms	932 KB	Output is correct
10	Correct	1 ms	1116 KB	Output is correct
11	Correct	1 ms	1116 KB	Output is correct
12	Correct	1 ms	1116 KB	Output is correct
13	Correct	1 ms	1180 KB	Output is correct
14	Correct	1 ms	1176 KB	Output is correct
15	Correct	1 ms	1116 KB	Output is correct
16	Correct	1 ms	1116 KB	Output is correct
17	Correct	1 ms	1116 KB	Output is correct
18	Correct	1 ms	1116 KB	Output is correct
19	Correct	1 ms	1116 KB	Output is correct
20	Correct	4 ms	1372 KB	Output is correct
21	Correct	1 ms	1116 KB	Output is correct
22	Correct	1 ms	1032 KB	Output is correct
23	Correct	1 ms	1116 KB	Output is correct
24	Correct	2 ms	1368 KB	Output is correct
25	Correct	1 ms	1372 KB	Output is correct
26	Correct	4 ms	1116 KB	Output is correct
27	Correct	3 ms	1116 KB	Output is correct
28	Correct	1 ms	1116 KB	Output is correct
29	Correct	2 ms	1848 KB	Output is correct
30	Correct	1 ms	1372 KB	Output is correct
31	Correct	1 ms	1372 KB	Output is correct
32	Correct	1 ms	1372 KB	Output is correct
33	Correct	3 ms	1884 KB	Output is correct
34	Correct	3 ms	1884 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1116 KB	Output is correct
2	Correct	1 ms	1112 KB	Output is correct
3	Correct	0 ms	1116 KB	Output is correct
4	Correct	0 ms	1116 KB	Output is correct
5	Correct	1 ms	1116 KB	Output is correct
6	Correct	1 ms	1116 KB	Output is correct
7	Correct	0 ms	1116 KB	Output is correct
8	Correct	0 ms	1116 KB	Output is correct
9	Correct	1 ms	1112 KB	Output is correct
10	Correct	1 ms	1116 KB	Output is correct
11	Correct	1 ms	1116 KB	Output is correct
12	Correct	1 ms	1116 KB	Output is correct
13	Correct	1 ms	1112 KB	Output is correct
14	Correct	1 ms	1116 KB	Output is correct
15	Correct	1 ms	1116 KB	Output is correct
16	Correct	1 ms	1116 KB	Output is correct
17	Correct	1 ms	1116 KB	Output is correct
18	Correct	1 ms	1116 KB	Output is correct
19	Correct	1 ms	1116 KB	Output is correct
20	Correct	4 ms	1368 KB	Output is correct
21	Correct	1 ms	1116 KB	Output is correct
22	Correct	1 ms	1116 KB	Output is correct
23	Correct	1 ms	1116 KB	Output is correct
24	Correct	2 ms	1372 KB	Output is correct
25	Correct	2 ms	1208 KB	Output is correct
26	Correct	3 ms	1112 KB	Output is correct
27	Correct	3 ms	1324 KB	Output is correct
28	Correct	1 ms	1116 KB	Output is correct
29	Correct	2 ms	1628 KB	Output is correct
30	Correct	1 ms	1372 KB	Output is correct
31	Correct	2 ms	1372 KB	Output is correct
32	Correct	1 ms	1372 KB	Output is correct
33	Correct	3 ms	1884 KB	Output is correct
34	Correct	3 ms	1884 KB	Output is correct
35	Correct	5 ms	2248 KB	Output is correct
36	Correct	2 ms	1372 KB	Output is correct
37	Correct	4 ms	2140 KB	Output is correct
38	Correct	6 ms	2648 KB	Output is correct
39	Correct	6 ms	2396 KB	Output is correct
40	Correct	6 ms	2648 KB	Output is correct
41	Correct	6 ms	2392 KB	Output is correct
42	Correct	43 ms	2012 KB	Output is correct
43	Correct	44 ms	2008 KB	Output is correct
44	Correct	43 ms	2048 KB	Output is correct
45	Correct	6 ms	2652 KB	Output is correct
46	Correct	5 ms	2716 KB	Output is correct

Subtask #5
43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1116 KB	Output is correct
2	Correct	1 ms	1116 KB	Output is correct
3	Correct	0 ms	1116 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	0 ms	1116 KB	Output is correct
6	Correct	1 ms	1116 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	1 ms	1116 KB	Output is correct
10	Correct	1 ms	1116 KB	Output is correct
11	Correct	1 ms	1184 KB	Output is correct
12	Correct	1 ms	1116 KB	Output is correct
13	Correct	1 ms	1112 KB	Output is correct
14	Correct	1 ms	1176 KB	Output is correct
15	Correct	1 ms	1176 KB	Output is correct
16	Correct	1 ms	1116 KB	Output is correct
17	Correct	1 ms	1368 KB	Output is correct
18	Correct	1 ms	1116 KB	Output is correct
19	Correct	1 ms	1116 KB	Output is correct
20	Correct	4 ms	1372 KB	Output is correct
21	Correct	1 ms	1116 KB	Output is correct
22	Correct	1 ms	1116 KB	Output is correct
23	Correct	1 ms	1116 KB	Output is correct
24	Correct	1 ms	1372 KB	Output is correct
25	Correct	1 ms	1372 KB	Output is correct
26	Correct	3 ms	1320 KB	Output is correct
27	Correct	3 ms	1116 KB	Output is correct
28	Correct	1 ms	1116 KB	Output is correct
29	Correct	2 ms	1628 KB	Output is correct
30	Correct	1 ms	1372 KB	Output is correct
31	Correct	1 ms	1372 KB	Output is correct
32	Correct	1 ms	1372 KB	Output is correct
33	Correct	3 ms	1884 KB	Output is correct
34	Correct	3 ms	1884 KB	Output is correct
35	Correct	5 ms	2140 KB	Output is correct
36	Correct	1 ms	1372 KB	Output is correct
37	Correct	5 ms	2140 KB	Output is correct
38	Correct	6 ms	2652 KB	Output is correct
39	Correct	6 ms	2396 KB	Output is correct
40	Correct	6 ms	2652 KB	Output is correct
41	Correct	6 ms	2636 KB	Output is correct
42	Correct	43 ms	2012 KB	Output is correct
43	Correct	43 ms	2012 KB	Output is correct
44	Correct	43 ms	2052 KB	Output is correct
45	Correct	6 ms	2648 KB	Output is correct
46	Correct	6 ms	2648 KB	Output is correct
47	Correct	16 ms	4956 KB	Output is correct
48	Correct	5 ms	2392 KB	Output is correct
49	Correct	4 ms	2396 KB	Output is correct
50	Correct	3 ms	2124 KB	Output is correct
51	Correct	25 ms	6848 KB	Output is correct
52	Correct	26 ms	6484 KB	Output is correct
53	Correct	12 ms	5208 KB	Output is correct
54	Correct	3 ms	2140 KB	Output is correct
55	Correct	3 ms	2140 KB	Output is correct
56	Correct	608 ms	4696 KB	Output is correct
57	Correct	49 ms	11092 KB	Output is correct
58	Correct	596 ms	3040 KB	Output is correct
59	Correct	593 ms	3036 KB	Output is correct
60	Correct	564 ms	3292 KB	Output is correct
61	Correct	541 ms	3292 KB	Output is correct
62	Correct	7 ms	2908 KB	Output is correct
63	Correct	36 ms	10660 KB	Output is correct
64	Correct	38 ms	10836 KB	Output is correct
65	Correct	49 ms	12376 KB	Output is correct
66	Correct	60 ms	16720 KB	Output is correct
67	Correct	64 ms	16724 KB	Output is correct

답안 #998879

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.0 / 21.0

Subtask #5 43.0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
21.0 / 21.0

Subtask #5
43.0 / 43.0