oj.uz

Submission #735357

# Submission time Handle Problem Language Result Execution time Memory
735357 2023-05-04T03:46:22 Z ReLice Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 229 ms 262144 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define bc back()
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}*/
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e9+7;
const ll mod=1e9+7;
const ll N=2e3+7;
ll n,l,r,d[N];
vector <vector <pair<ll,ll>> > g(N);
void dijkstra(ll val){
    set <pair<ll,ll>> q;
    q.insert({0,val});
    d[val]=0;
    while(!q.empty()){
        ll x=q.begin()->sc;
        q.erase(q.begin());
        for(auto i : g[x]){
            ll len=i.sc,to=i.fr;
            if(d[to]>d[x]+len){
                d[to]=d[x]+len;
                q.insert({d[to],to});
            }
        }
    }
}
void solve(){
    ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
    ll k;
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>b>>t;
        if(i==0) k=b;
        if(i==1) q=b;
        c=0;
        for(j=b+t;j<n;j+=t){
            c++;
            g[b].pb({j,c});
        }
        c=0;
        for(j=b-t;j>=0;j-=t){
            c++;
            g[b].pb({j,c});
        }
    }
    for(i=0;i<n;i++) d[i]=inf;
    dijkstra(k);
    if(d[q]==inf) cout<<-1<<endl;
    else cout<<d[q]<<endl;
}
signed main(){
    //start();
    //fre("");
    ll t=1;
    //cin>>t;
    while(t--) solve();
}
/*
5 3
0 2
1 1
4 1
*/

Compilation message

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:44:14: warning: unused variable 'sum' [-Wunused-variable]
   44 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |              ^~~
skyscraper.cpp:44:20: warning: unused variable 'ans' [-Wunused-variable]
   44 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |                    ^~~
skyscraper.cpp:44:28: warning: unused variable 'mx' [-Wunused-variable]
   44 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |                            ^~
skyscraper.cpp:63:13: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     dijkstra(k);
      |     ~~~~~~~~^~~
skyscraper.cpp:64:11: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     if(d[q]==inf) cout<<-1<<endl;
      |        ~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 356 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 6 ms 4548 KB Output is correct
13 Correct 6 ms 4548 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 6 ms 4548 KB Output is correct
13 Correct 5 ms 4548 KB Output is correct
14 Correct 1 ms 360 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 72 ms 64524 KB Output is correct
21 Correct 1 ms 356 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 724 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 89 ms 66396 KB Output is correct
27 Correct 84 ms 66236 KB Output is correct
28 Correct 2 ms 724 KB Output is correct
29 Correct 4 ms 2132 KB Output is correct
30 Correct 2 ms 980 KB Output is correct
31 Correct 3 ms 1380 KB Output is correct
32 Correct 2 ms 980 KB Output is correct
33 Correct 6 ms 3280 KB Output is correct
34 Correct 6 ms 3408 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 356 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 6 ms 4548 KB Output is correct
13 Correct 6 ms 4548 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 69 ms 64596 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 360 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 2 ms 748 KB Output is correct
25 Correct 3 ms 596 KB Output is correct
26 Correct 87 ms 66300 KB Output is correct
27 Correct 83 ms 66192 KB Output is correct
28 Correct 2 ms 724 KB Output is correct
29 Correct 4 ms 2132 KB Output is correct
30 Correct 2 ms 988 KB Output is correct
31 Correct 3 ms 1364 KB Output is correct
32 Correct 2 ms 980 KB Output is correct
33 Correct 7 ms 3296 KB Output is correct
34 Correct 6 ms 3428 KB Output is correct
35 Correct 16 ms 3532 KB Output is correct
36 Correct 4 ms 724 KB Output is correct
37 Correct 17 ms 6780 KB Output is correct
38 Correct 21 ms 5516 KB Output is correct
39 Correct 21 ms 5844 KB Output is correct
40 Correct 21 ms 5616 KB Output is correct
41 Correct 20 ms 5380 KB Output is correct
42 Runtime error 227 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 5 ms 4548 KB Output is correct
13 Correct 5 ms 4548 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 360 KB Output is correct
16 Correct 1 ms 356 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 71 ms 64616 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 3 ms 724 KB Output is correct
25 Correct 3 ms 596 KB Output is correct
26 Correct 89 ms 66336 KB Output is correct
27 Correct 83 ms 66288 KB Output is correct
28 Correct 2 ms 744 KB Output is correct
29 Correct 4 ms 2132 KB Output is correct
30 Correct 2 ms 1084 KB Output is correct
31 Correct 3 ms 1364 KB Output is correct
32 Correct 2 ms 980 KB Output is correct
33 Correct 6 ms 3280 KB Output is correct
34 Correct 7 ms 3424 KB Output is correct
35 Correct 16 ms 3560 KB Output is correct
36 Correct 3 ms 724 KB Output is correct
37 Correct 18 ms 6732 KB Output is correct
38 Correct 21 ms 5488 KB Output is correct
39 Correct 21 ms 5784 KB Output is correct
40 Correct 21 ms 5688 KB Output is correct
41 Correct 22 ms 5324 KB Output is correct
42 Runtime error 229 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -