oj.uz

Submission #735363

# Submission time Handle Problem Language Result Execution time Memory
735363 2023-05-04T04:03:51 Z ReLice Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 122 ms 48460 KB 
#include <bits/stdc++.h>
#define ll int
#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];
int edge[N][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){
                q.erase({d[to], to});
                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;
    memset(edge, -1, sizeof(edge));
    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++;
            if (edge[b][j] == -1 || edge[b][j] > c) {
                edge[b][j] = c;
            }
        }
        c=0;
        for(j=b-t;j>=0;j-=t){
            c++;
            if (edge[b][j] == -1 || edge[b][j] > c) {
                edge[b][j] = c;
            }
        }
    }
    for (int a = 0; a < n; ++a) {
        for (int b = 0; b < n; ++b) {
            if (edge[a][b] == -1) {
                continue;
            }
            g[a].push_back({b, edge[a][b]});
        }
    }
    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:46:14: warning: unused variable 'sum' [-Wunused-variable]
   46 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |              ^~~
skyscraper.cpp:46:20: warning: unused variable 'ans' [-Wunused-variable]
   46 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |                    ^~~
skyscraper.cpp:46:28: warning: unused variable 'mx' [-Wunused-variable]
   46 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |                            ^~
skyscraper.cpp:78:13: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |     dijkstra(k);
      |     ~~~~~~~~^~~
skyscraper.cpp:79:11: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |     if(d[q]==inf) cout<<-1<<endl;
      |        ~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16084 KB Output is correct
2 Correct 6 ms 16084 KB Output is correct
3 Correct 7 ms 16084 KB Output is correct
4 Correct 7 ms 16120 KB Output is correct
5 Correct 9 ms 16028 KB Output is correct
6 Correct 7 ms 16084 KB Output is correct
7 Correct 8 ms 16084 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 7 ms 16084 KB Output is correct
3 Correct 6 ms 16084 KB Output is correct
4 Correct 7 ms 16084 KB Output is correct
5 Correct 7 ms 16084 KB Output is correct
6 Correct 7 ms 16084 KB Output is correct
7 Correct 8 ms 16116 KB Output is correct
8 Correct 7 ms 16084 KB Output is correct
9 Correct 7 ms 16084 KB Output is correct
10 Correct 9 ms 16076 KB Output is correct
11 Correct 9 ms 16084 KB Output is correct
12 Correct 9 ms 16092 KB Output is correct
13 Correct 10 ms 16212 KB Output is correct
14 Correct 8 ms 16084 KB Output is correct
15 Correct 9 ms 16084 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 8 ms 16084 KB Output is correct
3 Correct 7 ms 16084 KB Output is correct
4 Correct 7 ms 16084 KB Output is correct
5 Correct 7 ms 16084 KB Output is correct
6 Correct 7 ms 16084 KB Output is correct
7 Correct 7 ms 16084 KB Output is correct
8 Correct 8 ms 16084 KB Output is correct
9 Correct 8 ms 16128 KB Output is correct
10 Correct 10 ms 16080 KB Output is correct
11 Correct 8 ms 16128 KB Output is correct
12 Correct 9 ms 16040 KB Output is correct
13 Correct 9 ms 16156 KB Output is correct
14 Correct 7 ms 16084 KB Output is correct
15 Correct 8 ms 16084 KB Output is correct
16 Correct 8 ms 16084 KB Output is correct
17 Correct 10 ms 16340 KB Output is correct
18 Correct 12 ms 16172 KB Output is correct
19 Correct 10 ms 16152 KB Output is correct
20 Correct 73 ms 48252 KB Output is correct
21 Correct 9 ms 16072 KB Output is correct
22 Correct 11 ms 16112 KB Output is correct
23 Correct 11 ms 16212 KB Output is correct
24 Correct 12 ms 16212 KB Output is correct
25 Correct 11 ms 16264 KB Output is correct
26 Correct 12 ms 16212 KB Output is correct
27 Correct 12 ms 16212 KB Output is correct
28 Correct 11 ms 16340 KB Output is correct
29 Correct 12 ms 16432 KB Output is correct
30 Correct 10 ms 16340 KB Output is correct
31 Correct 12 ms 16468 KB Output is correct
32 Correct 10 ms 16432 KB Output is correct
33 Correct 13 ms 16640 KB Output is correct
34 Correct 13 ms 16596 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 7 ms 16028 KB Output is correct
3 Correct 7 ms 16084 KB Output is correct
4 Correct 7 ms 16084 KB Output is correct
5 Correct 7 ms 16084 KB Output is correct
6 Correct 8 ms 16084 KB Output is correct
7 Correct 7 ms 16072 KB Output is correct
8 Correct 7 ms 16084 KB Output is correct
9 Correct 8 ms 16120 KB Output is correct
10 Correct 7 ms 16084 KB Output is correct
11 Correct 9 ms 16084 KB Output is correct
12 Correct 10 ms 16160 KB Output is correct
13 Correct 8 ms 16212 KB Output is correct
14 Correct 7 ms 16084 KB Output is correct
15 Correct 8 ms 16084 KB Output is correct
16 Correct 7 ms 16136 KB Output is correct
17 Correct 10 ms 16340 KB Output is correct
18 Correct 9 ms 16100 KB Output is correct
19 Correct 9 ms 16084 KB Output is correct
20 Correct 71 ms 48164 KB Output is correct
21 Correct 7 ms 16084 KB Output is correct
22 Correct 9 ms 16168 KB Output is correct
23 Correct 10 ms 16140 KB Output is correct
24 Correct 12 ms 16248 KB Output is correct
25 Correct 11 ms 16172 KB Output is correct
26 Correct 14 ms 16200 KB Output is correct
27 Correct 12 ms 16140 KB Output is correct
28 Correct 12 ms 16244 KB Output is correct
29 Correct 13 ms 16496 KB Output is correct
30 Correct 11 ms 16340 KB Output is correct
31 Correct 12 ms 16468 KB Output is correct
32 Correct 10 ms 16340 KB Output is correct
33 Correct 12 ms 16596 KB Output is correct
34 Correct 12 ms 16596 KB Output is correct
35 Correct 26 ms 17492 KB Output is correct
36 Correct 11 ms 16340 KB Output is correct
37 Correct 27 ms 18928 KB Output is correct
38 Correct 30 ms 18424 KB Output is correct
39 Correct 30 ms 18592 KB Output is correct
40 Correct 33 ms 18492 KB Output is correct
41 Correct 33 ms 18272 KB Output is correct
42 Correct 83 ms 16228 KB Output is correct
43 Correct 60 ms 16308 KB Output is correct
44 Correct 122 ms 48436 KB Output is correct
45 Correct 30 ms 18652 KB Output is correct
46 Correct 37 ms 18600 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 8 ms 16004 KB Output is correct
3 Correct 7 ms 16084 KB Output is correct
4 Correct 7 ms 16084 KB Output is correct
5 Correct 7 ms 16028 KB Output is correct
6 Correct 7 ms 16120 KB Output is correct
7 Correct 7 ms 16116 KB Output is correct
8 Correct 7 ms 16084 KB Output is correct
9 Correct 7 ms 16084 KB Output is correct
10 Correct 8 ms 16096 KB Output is correct
11 Correct 8 ms 16076 KB Output is correct
12 Correct 10 ms 16024 KB Output is correct
13 Correct 8 ms 16184 KB Output is correct
14 Correct 11 ms 16092 KB Output is correct
15 Correct 10 ms 16128 KB Output is correct
16 Correct 8 ms 16084 KB Output is correct
17 Correct 10 ms 16340 KB Output is correct
18 Correct 10 ms 16084 KB Output is correct
19 Correct 12 ms 16084 KB Output is correct
20 Correct 71 ms 48180 KB Output is correct
21 Correct 7 ms 16084 KB Output is correct
22 Correct 9 ms 16080 KB Output is correct
23 Correct 9 ms 16212 KB Output is correct
24 Correct 12 ms 16244 KB Output is correct
25 Correct 11 ms 16244 KB Output is correct
26 Correct 13 ms 16248 KB Output is correct
27 Correct 13 ms 16116 KB Output is correct
28 Correct 10 ms 16248 KB Output is correct
29 Correct 14 ms 16540 KB Output is correct
30 Correct 11 ms 16356 KB Output is correct
31 Correct 10 ms 16420 KB Output is correct
32 Correct 11 ms 16340 KB Output is correct
33 Correct 13 ms 16720 KB Output is correct
34 Correct 12 ms 16596 KB Output is correct
35 Correct 25 ms 17528 KB Output is correct
36 Correct 12 ms 16268 KB Output is correct
37 Correct 29 ms 19000 KB Output is correct
38 Correct 31 ms 18420 KB Output is correct
39 Correct 30 ms 18552 KB Output is correct
40 Correct 30 ms 18428 KB Output is correct
41 Correct 30 ms 18288 KB Output is correct
42 Correct 67 ms 16236 KB Output is correct
43 Correct 60 ms 16348 KB Output is correct
44 Correct 113 ms 48460 KB Output is correct
45 Correct 26 ms 18660 KB Output is correct
46 Correct 30 ms 18644 KB Output is correct
47 Runtime error 20 ms 32492 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -