oj.uz

Submission #563105

# Submission time Handle Problem Language Result Execution time Memory
563105 2022-05-16T08:50:39 Z khangal Jakarta Skyscrapers (APIO15_skyscraper) C++14
100 / 100
 698 ms 41944 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<long long> vl;
typedef pair<long long, long long > pl;
const int N = 1e6 + 1;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18    
#define MIN -1e18
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n, m, mid, res,pos, mn, mx, sum, h1, h2, arr[3234567],arr1[1234567],k, i, j, h, a, x, y, z,par[1234567];
bool used[1234567];
ll tp[1234567];
ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123];
//ll jump[22][223456];
//ll lvl[1234567];
//ll bit[1234567];
//ll timer;
//ll st[1234567],endd[1234567];
//ll dp[5005][5005];
vl dog[1234567];
ll dist[1234567];
priority_queue<pl> pq;
void go(ll node){
    used[node]=1;
    for(auto u:dog[node]){
        for(int i=node+u,a=1;i<n;i+=u,a++){
            if(dist[i] > dist[node] + a){
                dist[i] = dist[node]+a;
                pq.push({-dist[i] , i});
            }
        }
        for(int i=node-u,a=1;i>=0;i-=u,a++){
            if(dist[i] > dist[node] + a){
                dist[i] = dist[node]+a;
                pq.push({-dist[i] , i});
            }
        }
        
    }
}
class A {  
public :
    static void funcA() {
        cin>>n>>m;
        ll st,en,b,p;
        cin>>st>>p;
        dog[st] . pb(p);
        cin>>en>>p;
        dog[en] . pb(p);
        m-=2;
        while(m--){
            cin>>b>>p;
            dog[b].pb(p);
        }
        for(int i=0;i<=1e6;i++)dist[i]=MAX;
        pq.push({0,st});
        dist[st]=0;
        while(pq.size()>0){
            ll a = pq.top().ss;
            pq.pop();
            if(a==en){
                cout<<dist[en];
                exit(0);
            }
            if(used[a]==0){
                go(a);
            }
        }
        cout<<-1;
    }
}lol;
void solve() {
    A::funcA();
}
int main() {
    ll T = 1;
    //cin>>T;
    boost;
    while (T--) {   
        solve();
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37204 KB Output is correct
2 Correct 18 ms 37076 KB Output is correct
3 Correct 18 ms 37080 KB Output is correct
4 Correct 18 ms 37116 KB Output is correct
5 Correct 18 ms 37044 KB Output is correct
6 Correct 18 ms 37132 KB Output is correct
7 Correct 19 ms 37140 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37076 KB Output is correct
2 Correct 18 ms 37120 KB Output is correct
3 Correct 18 ms 37144 KB Output is correct
4 Correct 18 ms 37124 KB Output is correct
5 Correct 18 ms 37148 KB Output is correct
6 Correct 18 ms 37100 KB Output is correct
7 Correct 19 ms 37076 KB Output is correct
8 Correct 18 ms 37116 KB Output is correct
9 Correct 20 ms 37116 KB Output is correct
10 Correct 18 ms 37164 KB Output is correct
11 Correct 19 ms 37076 KB Output is correct
12 Correct 19 ms 37188 KB Output is correct
13 Correct 19 ms 37128 KB Output is correct
14 Correct 18 ms 37204 KB Output is correct
15 Correct 19 ms 37112 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37124 KB Output is correct
2 Correct 18 ms 37076 KB Output is correct
3 Correct 18 ms 37108 KB Output is correct
4 Correct 18 ms 37112 KB Output is correct
5 Correct 18 ms 37120 KB Output is correct
6 Correct 19 ms 37128 KB Output is correct
7 Correct 18 ms 37076 KB Output is correct
8 Correct 19 ms 37076 KB Output is correct
9 Correct 18 ms 37076 KB Output is correct
10 Correct 18 ms 37076 KB Output is correct
11 Correct 19 ms 37124 KB Output is correct
12 Correct 19 ms 37068 KB Output is correct
13 Correct 21 ms 37080 KB Output is correct
14 Correct 19 ms 37128 KB Output is correct
15 Correct 20 ms 37128 KB Output is correct
16 Correct 19 ms 37104 KB Output is correct
17 Correct 20 ms 37128 KB Output is correct
18 Correct 18 ms 37068 KB Output is correct
19 Correct 20 ms 37036 KB Output is correct
20 Correct 23 ms 37204 KB Output is correct
21 Correct 19 ms 37076 KB Output is correct
22 Correct 18 ms 37160 KB Output is correct
23 Correct 19 ms 37204 KB Output is correct
24 Correct 20 ms 37204 KB Output is correct
25 Correct 21 ms 37136 KB Output is correct
26 Correct 19 ms 37132 KB Output is correct
27 Correct 20 ms 37156 KB Output is correct
28 Correct 20 ms 37168 KB Output is correct
29 Correct 20 ms 37332 KB Output is correct
30 Correct 19 ms 37332 KB Output is correct
31 Correct 22 ms 37332 KB Output is correct
32 Correct 20 ms 37332 KB Output is correct
33 Correct 20 ms 37404 KB Output is correct
34 Correct 21 ms 37544 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37076 KB Output is correct
2 Correct 18 ms 37076 KB Output is correct
3 Correct 18 ms 37116 KB Output is correct
4 Correct 18 ms 37144 KB Output is correct
5 Correct 19 ms 37052 KB Output is correct
6 Correct 18 ms 37076 KB Output is correct
7 Correct 19 ms 37076 KB Output is correct
8 Correct 18 ms 37096 KB Output is correct
9 Correct 18 ms 37076 KB Output is correct
10 Correct 19 ms 37076 KB Output is correct
11 Correct 20 ms 37076 KB Output is correct
12 Correct 19 ms 37144 KB Output is correct
13 Correct 19 ms 37152 KB Output is correct
14 Correct 20 ms 37204 KB Output is correct
15 Correct 20 ms 37120 KB Output is correct
16 Correct 19 ms 37116 KB Output is correct
17 Correct 22 ms 37204 KB Output is correct
18 Correct 20 ms 37096 KB Output is correct
19 Correct 20 ms 37148 KB Output is correct
20 Correct 23 ms 37256 KB Output is correct
21 Correct 21 ms 37120 KB Output is correct
22 Correct 18 ms 37076 KB Output is correct
23 Correct 20 ms 37204 KB Output is correct
24 Correct 19 ms 37204 KB Output is correct
25 Correct 20 ms 37168 KB Output is correct
26 Correct 20 ms 37128 KB Output is correct
27 Correct 21 ms 37200 KB Output is correct
28 Correct 20 ms 37204 KB Output is correct
29 Correct 19 ms 37332 KB Output is correct
30 Correct 20 ms 37332 KB Output is correct
31 Correct 21 ms 37316 KB Output is correct
32 Correct 20 ms 37268 KB Output is correct
33 Correct 21 ms 37380 KB Output is correct
34 Correct 21 ms 37588 KB Output is correct
35 Correct 31 ms 37724 KB Output is correct
36 Correct 21 ms 37196 KB Output is correct
37 Correct 27 ms 37752 KB Output is correct
38 Correct 32 ms 37944 KB Output is correct
39 Correct 31 ms 37840 KB Output is correct
40 Correct 32 ms 38004 KB Output is correct
41 Correct 33 ms 37996 KB Output is correct
42 Correct 29 ms 37712 KB Output is correct
43 Correct 32 ms 37704 KB Output is correct
44 Correct 72 ms 37660 KB Output is correct
45 Correct 30 ms 37928 KB Output is correct
46 Correct 31 ms 37892 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37116 KB Output is correct
2 Correct 18 ms 37124 KB Output is correct
3 Correct 18 ms 37076 KB Output is correct
4 Correct 20 ms 37124 KB Output is correct
5 Correct 20 ms 37076 KB Output is correct
6 Correct 19 ms 37076 KB Output is correct
7 Correct 18 ms 37068 KB Output is correct
8 Correct 19 ms 37120 KB Output is correct
9 Correct 18 ms 37120 KB Output is correct
10 Correct 20 ms 37116 KB Output is correct
11 Correct 19 ms 37076 KB Output is correct
12 Correct 19 ms 37128 KB Output is correct
13 Correct 19 ms 37068 KB Output is correct
14 Correct 19 ms 37128 KB Output is correct
15 Correct 22 ms 37080 KB Output is correct
16 Correct 20 ms 37248 KB Output is correct
17 Correct 20 ms 37204 KB Output is correct
18 Correct 21 ms 37112 KB Output is correct
19 Correct 20 ms 37128 KB Output is correct
20 Correct 23 ms 37332 KB Output is correct
21 Correct 18 ms 37120 KB Output is correct
22 Correct 19 ms 37176 KB Output is correct
23 Correct 21 ms 37204 KB Output is correct
24 Correct 19 ms 37148 KB Output is correct
25 Correct 20 ms 37220 KB Output is correct
26 Correct 19 ms 37144 KB Output is correct
27 Correct 19 ms 37204 KB Output is correct
28 Correct 19 ms 37196 KB Output is correct
29 Correct 20 ms 37388 KB Output is correct
30 Correct 18 ms 37296 KB Output is correct
31 Correct 19 ms 37364 KB Output is correct
32 Correct 19 ms 37332 KB Output is correct
33 Correct 20 ms 37440 KB Output is correct
34 Correct 21 ms 37460 KB Output is correct
35 Correct 31 ms 37844 KB Output is correct
36 Correct 20 ms 37204 KB Output is correct
37 Correct 27 ms 37768 KB Output is correct
38 Correct 32 ms 38060 KB Output is correct
39 Correct 31 ms 37820 KB Output is correct
40 Correct 32 ms 37988 KB Output is correct
41 Correct 33 ms 37972 KB Output is correct
42 Correct 28 ms 37672 KB Output is correct
43 Correct 34 ms 37676 KB Output is correct
44 Correct 73 ms 37576 KB Output is correct
45 Correct 31 ms 37900 KB Output is correct
46 Correct 35 ms 37888 KB Output is correct
47 Correct 31 ms 38952 KB Output is correct
48 Correct 30 ms 37860 KB Output is correct
49 Correct 30 ms 37764 KB Output is correct
50 Correct 28 ms 37608 KB Output is correct
51 Correct 42 ms 40300 KB Output is correct
52 Correct 44 ms 39376 KB Output is correct
53 Correct 36 ms 38404 KB Output is correct
54 Correct 20 ms 37500 KB Output is correct
55 Correct 20 ms 37460 KB Output is correct
56 Correct 695 ms 38924 KB Output is correct
57 Correct 24 ms 39372 KB Output is correct
58 Correct 698 ms 37904 KB Output is correct
59 Correct 31 ms 37940 KB Output is correct
60 Correct 31 ms 38020 KB Output is correct
61 Correct 32 ms 38012 KB Output is correct
62 Correct 37 ms 38388 KB Output is correct
63 Correct 49 ms 40004 KB Output is correct
64 Correct 46 ms 39984 KB Output is correct
65 Correct 50 ms 39924 KB Output is correct
66 Correct 58 ms 41944 KB Output is correct
67 Correct 51 ms 41916 KB Output is correct