oj.uz

Submission #838442

# Submission time Handle Problem Language Result Execution time Memory
838442 2023-08-27T00:02:34 Z PenguinsAreCute Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 223 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
typedef pair<int,ii> iii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define HASTC 0
#define BSIZE 200
vector<pair<ii,int>> adj[30069][BSIZE+5];
int dist[30069][BSIZE+5];
void dijkstra(ii s) {
    priority_queue<iii,vector<iii>,greater<iii>> pq;
    REP(i,0,30069) REP(j,0,BSIZE+5) dist[i][j]=1210201042069;
    dist[s.fi][s.se]=0; pq.push(iii(0,s));
    while(!pq.empty()) {
        iii c=pq.top(); pq.pop();
        if(c.fi!=dist[c.se.fi][c.se.se]) continue;
        for(auto i: adj[c.se.fi][c.se.se]) {
            if(dist[i.fi.fi][i.fi.se]>c.fi+i.se) {
                dist[i.fi.fi][i.fi.se]=c.fi+i.se;
                pq.push(iii(dist[i.fi.fi][i.fi.se], i.fi));
            }
        }
    }
}
void solvetc(int idx) {
    int N, M, B, P; cin >> N >> M;
    ii s, d;
    REP(i,0,N) REP(j,1,BSIZE+1) {
        // connect pos pow to (pos+pow,pow),(pos-pow,pow),(pos+pow),(pos-pow)
        if(i-j>=0) {
            adj[i][j].pb(mp(mp(i-j,j),1));
            adj[i][j].pb(mp(mp(i-j,0),1));
        }
        if(i+j<N) {
            adj[i][j].pb(mp(mp(i+j,j),1));
            adj[i][j].pb(mp(mp(i+j,0),1));
        }
    }
    REP(i,0,M) {
        cin>>B>>P;
        if(i==0) s=mp(B,0);
        else if(i==1) d=mp(B,0);
        if(P<=BSIZE) {
            adj[B][0].pb(mp(mp(B,P),0));
            adj[B][P].pb(mp(mp(B,0),0));
        } else REP(i,-(B/P),(N-B-1)/P+1) adj[B][0].pb(mp(mp(P*i+B,0),abs(i)));
    }
    dijkstra(s);
    cout<<(dist[d.fi][d.se]!=1210201042069?dist[d.fi][d.se]:-1);
    
}
int32_t main() {
    int tc;
    if(HASTC) cin>>tc;
    else tc=1;
    for(int i=0;i<tc;i++) solvetc(i);    
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 193224 KB Output is correct
2 Correct 81 ms 193268 KB Output is correct
3 Correct 77 ms 193288 KB Output is correct
4 Correct 81 ms 193260 KB Output is correct
5 Correct 80 ms 193208 KB Output is correct
6 Correct 79 ms 193212 KB Output is correct
7 Correct 81 ms 193248 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 193288 KB Output is correct
2 Correct 81 ms 193296 KB Output is correct
3 Correct 81 ms 193320 KB Output is correct
4 Correct 79 ms 193260 KB Output is correct
5 Correct 83 ms 193236 KB Output is correct
6 Correct 79 ms 193292 KB Output is correct
7 Correct 80 ms 193244 KB Output is correct
8 Correct 79 ms 193376 KB Output is correct
9 Correct 81 ms 193484 KB Output is correct
10 Correct 81 ms 193828 KB Output is correct
11 Correct 82 ms 194124 KB Output is correct
12 Correct 82 ms 194044 KB Output is correct
13 Correct 81 ms 193996 KB Output is correct
14 Correct 81 ms 194096 KB Output is correct
15 Correct 81 ms 194140 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 193228 KB Output is correct
2 Correct 81 ms 193216 KB Output is correct
3 Correct 86 ms 193216 KB Output is correct
4 Correct 88 ms 193228 KB Output is correct
5 Correct 79 ms 193292 KB Output is correct
6 Correct 83 ms 193296 KB Output is correct
7 Correct 80 ms 193220 KB Output is correct
8 Correct 80 ms 193368 KB Output is correct
9 Correct 80 ms 193412 KB Output is correct
10 Correct 81 ms 193840 KB Output is correct
11 Correct 82 ms 194104 KB Output is correct
12 Correct 82 ms 193944 KB Output is correct
13 Correct 92 ms 193960 KB Output is correct
14 Correct 83 ms 194072 KB Output is correct
15 Correct 84 ms 194168 KB Output is correct
16 Correct 84 ms 195660 KB Output is correct
17 Correct 100 ms 207844 KB Output is correct
18 Correct 135 ms 229772 KB Output is correct
19 Correct 122 ms 235280 KB Output is correct
20 Correct 128 ms 235596 KB Output is correct
21 Correct 88 ms 200072 KB Output is correct
22 Correct 115 ms 230384 KB Output is correct
23 Correct 114 ms 226504 KB Output is correct
24 Correct 123 ms 233164 KB Output is correct
25 Correct 127 ms 235300 KB Output is correct
26 Correct 134 ms 235416 KB Output is correct
27 Correct 126 ms 235428 KB Output is correct
28 Correct 127 ms 235436 KB Output is correct
29 Correct 136 ms 235284 KB Output is correct
30 Correct 129 ms 235172 KB Output is correct
31 Correct 144 ms 235348 KB Output is correct
32 Correct 132 ms 235340 KB Output is correct
33 Correct 151 ms 235600 KB Output is correct
34 Correct 162 ms 235596 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 193296 KB Output is correct
2 Correct 89 ms 193180 KB Output is correct
3 Correct 91 ms 193188 KB Output is correct
4 Correct 80 ms 193188 KB Output is correct
5 Correct 86 ms 193296 KB Output is correct
6 Correct 80 ms 193296 KB Output is correct
7 Correct 80 ms 193272 KB Output is correct
8 Correct 80 ms 193300 KB Output is correct
9 Correct 95 ms 193424 KB Output is correct
10 Correct 86 ms 193992 KB Output is correct
11 Correct 86 ms 194120 KB Output is correct
12 Correct 82 ms 194040 KB Output is correct
13 Correct 88 ms 194008 KB Output is correct
14 Correct 86 ms 194076 KB Output is correct
15 Correct 85 ms 194052 KB Output is correct
16 Correct 86 ms 195808 KB Output is correct
17 Correct 102 ms 208016 KB Output is correct
18 Correct 118 ms 229660 KB Output is correct
19 Correct 123 ms 235292 KB Output is correct
20 Correct 130 ms 235668 KB Output is correct
21 Correct 89 ms 200044 KB Output is correct
22 Correct 116 ms 230476 KB Output is correct
23 Correct 115 ms 226464 KB Output is correct
24 Correct 146 ms 233196 KB Output is correct
25 Correct 124 ms 235564 KB Output is correct
26 Correct 130 ms 235316 KB Output is correct
27 Correct 124 ms 235432 KB Output is correct
28 Correct 128 ms 235344 KB Output is correct
29 Correct 138 ms 235292 KB Output is correct
30 Correct 132 ms 235216 KB Output is correct
31 Correct 133 ms 235340 KB Output is correct
32 Correct 127 ms 235280 KB Output is correct
33 Correct 151 ms 235480 KB Output is correct
34 Correct 153 ms 235596 KB Output is correct
35 Correct 143 ms 225568 KB Output is correct
36 Correct 113 ms 215592 KB Output is correct
37 Correct 176 ms 237532 KB Output is correct
38 Correct 178 ms 239088 KB Output is correct
39 Correct 172 ms 239116 KB Output is correct
40 Correct 173 ms 239132 KB Output is correct
41 Correct 174 ms 239108 KB Output is correct
42 Correct 138 ms 237140 KB Output is correct
43 Correct 132 ms 237004 KB Output is correct
44 Correct 138 ms 237192 KB Output is correct
45 Correct 221 ms 241488 KB Output is correct
46 Correct 219 ms 241468 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 193296 KB Output is correct
2 Correct 83 ms 193344 KB Output is correct
3 Correct 86 ms 193248 KB Output is correct
4 Correct 82 ms 193276 KB Output is correct
5 Correct 85 ms 193236 KB Output is correct
6 Correct 82 ms 193272 KB Output is correct
7 Correct 84 ms 193296 KB Output is correct
8 Correct 82 ms 193356 KB Output is correct
9 Correct 81 ms 193476 KB Output is correct
10 Correct 85 ms 193808 KB Output is correct
11 Correct 84 ms 194124 KB Output is correct
12 Correct 84 ms 193984 KB Output is correct
13 Correct 85 ms 194024 KB Output is correct
14 Correct 86 ms 194124 KB Output is correct
15 Correct 84 ms 194116 KB Output is correct
16 Correct 84 ms 195696 KB Output is correct
17 Correct 101 ms 207884 KB Output is correct
18 Correct 117 ms 229704 KB Output is correct
19 Correct 138 ms 235204 KB Output is correct
20 Correct 131 ms 235672 KB Output is correct
21 Correct 88 ms 200012 KB Output is correct
22 Correct 118 ms 230396 KB Output is correct
23 Correct 117 ms 226544 KB Output is correct
24 Correct 124 ms 233208 KB Output is correct
25 Correct 127 ms 235288 KB Output is correct
26 Correct 126 ms 235296 KB Output is correct
27 Correct 125 ms 235340 KB Output is correct
28 Correct 133 ms 235416 KB Output is correct
29 Correct 137 ms 235336 KB Output is correct
30 Correct 127 ms 235268 KB Output is correct
31 Correct 132 ms 235352 KB Output is correct
32 Correct 133 ms 235396 KB Output is correct
33 Correct 153 ms 235572 KB Output is correct
34 Correct 157 ms 235588 KB Output is correct
35 Correct 145 ms 225612 KB Output is correct
36 Correct 112 ms 215660 KB Output is correct
37 Correct 176 ms 237500 KB Output is correct
38 Correct 175 ms 239044 KB Output is correct
39 Correct 173 ms 239112 KB Output is correct
40 Correct 180 ms 239340 KB Output is correct
41 Correct 173 ms 239104 KB Output is correct
42 Correct 134 ms 237196 KB Output is correct
43 Correct 133 ms 236988 KB Output is correct
44 Correct 140 ms 237140 KB Output is correct
45 Correct 216 ms 241480 KB Output is correct
46 Correct 223 ms 241504 KB Output is correct
47 Runtime error 159 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -