oj.uz

Submission #228942

# Submission time Handle Problem Language Result Execution time Memory
228942 2020-05-03T06:35:50 Z mehrdad_sohrabi Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 1000 ms 24624 KB 
#include <bits/stdc++.h>
typedef int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=3e4+100,sq=173;
ll dis[N][sq];
set <pair <pii,int> > s;
vector <int> a[N];
ll p[N];
void dij(){
    while(s.size()){
        pii v=s.begin()->F;
        ll w=dis[v.F][v.S];
        s.erase(s.begin());
      //  cout << v.F << " " << v.S << " " << w << endl;
        if (v.S==0){
            for (auto e : a[v.F]){
                ll u=p[e];
                //cout << u << endl;
                if (u<sq){
                    if (dis[v.F][u]>w){
                        s.erase({{v.F,u},dis[v.F][u]});
                        dis[v.F][u]=w;
                        s.insert({{v.F,u},dis[v.F][u]});
                    }
                }
                else{
                    for (int i=-v.F/u;i<=N/sq;i++){
                        ll h=v.F+i*u;
                        if (h>=0 && h<N){
                            if (dis[h][0]>w+abs(i)){
                                s.erase({{h,0},dis[h][0]});
                                dis[h][0]=w+abs(i);
                                s.insert({{h,0},dis[h][0]});
                            }
                        }
                    }
                }
            }
            continue;
        }
        ll u=v.S;
        ll h=v.F+u;
        if (h>=0 && h<N && dis[h][0]>w+1){
            s.erase({{h,0},dis[h][0]});
            dis[h][0]=w+1;
            s.insert({{h,0},dis[h][0]});
        }
        if (h>=0 && h<N && dis[h][u]>w+1){
            s.erase({{h,u},dis[h][u]});
            dis[h][u]=w+1;
            s.insert({{h,u},dis[h][u]});
        }
        h=v.F-u;
        if (h>=0 && h<N && dis[h][0]>w+1){
            s.erase({{h,0},dis[h][0]});
            dis[h][0]=w+1;
            s.insert({{h,0},dis[h][0]});
        }
        if (h>=0 && h<N && dis[h][u]>w+1){
            s.erase({{h,u},dis[h][u]});
            dis[h][u]=w+1;
            s.insert({{h,u},dis[h][u]});
        }

    }
}
ll ja[N];
int32_t main(){
    sync;
    ll n,m;
    cin >> n >> m;
    for (int i=0;i<m;i++){
        ll x;
        cin >> x >> p[i];
        a[x].pb(i);
        ja[i]=x;
    }
    for (int i=0;i<N;i++){
        for (int j=0;j<sq;j++){
            dis[i][j]=2e8;
        }
    }
    dis[ja[0]][0]=0;
    s.insert({{ja[0],0},0});
    dij();
    ll x=ja[1];
    if (dis[x][0]>1e8) kill(-1);
    kill(dis[x][0]);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21504 KB Output is correct
2 Correct 18 ms 21376 KB Output is correct
3 Correct 15 ms 21376 KB Output is correct
4 Correct 15 ms 21504 KB Output is correct
5 Correct 23 ms 21376 KB Output is correct
6 Correct 23 ms 21376 KB Output is correct
7 Correct 19 ms 21504 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21504 KB Output is correct
2 Correct 19 ms 21504 KB Output is correct
3 Correct 15 ms 21376 KB Output is correct
4 Correct 16 ms 21376 KB Output is correct
5 Correct 23 ms 21376 KB Output is correct
6 Correct 23 ms 21504 KB Output is correct
7 Correct 19 ms 21376 KB Output is correct
8 Correct 29 ms 21504 KB Output is correct
9 Correct 48 ms 21496 KB Output is correct
10 Correct 138 ms 21504 KB Output is correct
11 Correct 384 ms 21504 KB Output is correct
12 Correct 36 ms 21504 KB Output is correct
13 Correct 19 ms 21504 KB Output is correct
14 Correct 506 ms 21752 KB Output is correct
15 Correct 494 ms 21752 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21504 KB Output is correct
2 Correct 18 ms 21376 KB Output is correct
3 Correct 15 ms 21376 KB Output is correct
4 Correct 15 ms 21376 KB Output is correct
5 Correct 23 ms 21376 KB Output is correct
6 Correct 22 ms 21376 KB Output is correct
7 Correct 18 ms 21376 KB Output is correct
8 Correct 26 ms 21504 KB Output is correct
9 Correct 48 ms 21504 KB Output is correct
10 Correct 142 ms 21512 KB Output is correct
11 Correct 382 ms 21504 KB Output is correct
12 Correct 36 ms 21504 KB Output is correct
13 Correct 18 ms 21504 KB Output is correct
14 Correct 498 ms 21632 KB Output is correct
15 Correct 498 ms 21752 KB Output is correct
16 Correct 15 ms 21504 KB Output is correct
17 Correct 243 ms 23288 KB Output is correct
18 Correct 14 ms 21504 KB Output is correct
19 Correct 17 ms 21504 KB Output is correct
20 Correct 19 ms 21504 KB Output is correct
21 Correct 15 ms 21504 KB Output is correct
22 Correct 15 ms 21504 KB Output is correct
23 Correct 83 ms 22648 KB Output is correct
24 Correct 146 ms 23100 KB Output is correct
25 Correct 53 ms 22912 KB Output is correct
26 Correct 52 ms 21504 KB Output is correct
27 Correct 44 ms 22016 KB Output is correct
28 Correct 106 ms 23160 KB Output is correct
29 Correct 232 ms 21624 KB Output is correct
30 Correct 64 ms 21376 KB Output is correct
31 Correct 126 ms 21624 KB Output is correct
32 Correct 91 ms 21624 KB Output is correct
33 Correct 496 ms 21752 KB Output is correct
34 Correct 515 ms 21752 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21504 KB Output is correct
2 Correct 18 ms 21376 KB Output is correct
3 Correct 15 ms 21376 KB Output is correct
4 Correct 15 ms 21376 KB Output is correct
5 Correct 23 ms 21376 KB Output is correct
6 Correct 23 ms 21376 KB Output is correct
7 Correct 23 ms 21376 KB Output is correct
8 Correct 27 ms 21504 KB Output is correct
9 Correct 46 ms 21376 KB Output is correct
10 Correct 135 ms 21504 KB Output is correct
11 Correct 386 ms 21624 KB Output is correct
12 Correct 36 ms 21504 KB Output is correct
13 Correct 18 ms 21504 KB Output is correct
14 Correct 495 ms 21636 KB Output is correct
15 Correct 512 ms 21752 KB Output is correct
16 Correct 14 ms 21504 KB Output is correct
17 Correct 245 ms 23288 KB Output is correct
18 Correct 14 ms 21504 KB Output is correct
19 Correct 15 ms 21504 KB Output is correct
20 Correct 18 ms 21504 KB Output is correct
21 Correct 14 ms 21504 KB Output is correct
22 Correct 14 ms 21504 KB Output is correct
23 Correct 86 ms 22648 KB Output is correct
24 Correct 150 ms 23188 KB Output is correct
25 Correct 48 ms 22912 KB Output is correct
26 Correct 50 ms 21632 KB Output is correct
27 Correct 45 ms 22016 KB Output is correct
28 Correct 104 ms 23168 KB Output is correct
29 Correct 227 ms 21504 KB Output is correct
30 Correct 64 ms 21376 KB Output is correct
31 Correct 123 ms 21624 KB Output is correct
32 Correct 95 ms 21528 KB Output is correct
33 Correct 503 ms 21752 KB Output is correct
34 Correct 499 ms 21752 KB Output is correct
35 Correct 590 ms 23672 KB Output is correct
36 Correct 186 ms 23416 KB Output is correct
37 Correct 732 ms 23672 KB Output is correct
38 Correct 654 ms 23928 KB Output is correct
39 Correct 659 ms 23804 KB Output is correct
40 Correct 640 ms 23860 KB Output is correct
41 Correct 603 ms 23932 KB Output is correct
42 Correct 54 ms 21888 KB Output is correct
43 Correct 52 ms 22392 KB Output is correct
44 Correct 23 ms 21888 KB Output is correct
45 Execution timed out 1084 ms 24624 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21376 KB Output is correct
2 Correct 18 ms 21376 KB Output is correct
3 Correct 16 ms 21504 KB Output is correct
4 Correct 14 ms 21376 KB Output is correct
5 Correct 23 ms 21376 KB Output is correct
6 Correct 22 ms 21504 KB Output is correct
7 Correct 18 ms 21376 KB Output is correct
8 Correct 26 ms 21376 KB Output is correct
9 Correct 45 ms 21504 KB Output is correct
10 Correct 139 ms 21624 KB Output is correct
11 Correct 390 ms 21624 KB Output is correct
12 Correct 37 ms 21504 KB Output is correct
13 Correct 19 ms 21504 KB Output is correct
14 Correct 494 ms 21700 KB Output is correct
15 Correct 497 ms 21752 KB Output is correct
16 Correct 15 ms 21504 KB Output is correct
17 Correct 252 ms 23288 KB Output is correct
18 Correct 16 ms 21504 KB Output is correct
19 Correct 14 ms 21504 KB Output is correct
20 Correct 20 ms 21504 KB Output is correct
21 Correct 15 ms 21504 KB Output is correct
22 Correct 15 ms 21504 KB Output is correct
23 Correct 84 ms 22648 KB Output is correct
24 Correct 143 ms 23032 KB Output is correct
25 Correct 50 ms 23032 KB Output is correct
26 Correct 54 ms 21632 KB Output is correct
27 Correct 44 ms 22016 KB Output is correct
28 Correct 103 ms 23288 KB Output is correct
29 Correct 224 ms 21504 KB Output is correct
30 Correct 65 ms 21376 KB Output is correct
31 Correct 135 ms 21504 KB Output is correct
32 Correct 89 ms 21624 KB Output is correct
33 Correct 498 ms 21752 KB Output is correct
34 Correct 504 ms 21752 KB Output is correct
35 Correct 592 ms 23800 KB Output is correct
36 Correct 187 ms 23416 KB Output is correct
37 Correct 760 ms 23800 KB Output is correct
38 Correct 683 ms 23928 KB Output is correct
39 Correct 666 ms 23832 KB Output is correct
40 Correct 650 ms 23832 KB Output is correct
41 Correct 613 ms 23928 KB Output is correct
42 Correct 56 ms 21888 KB Output is correct
43 Correct 49 ms 22400 KB Output is correct
44 Correct 23 ms 21888 KB Output is correct
45 Execution timed out 1092 ms 24568 KB Time limit exceeded
46 Halted 0 ms 0 KB -