Submission #735363

#	Time	Username	Problem	Language	Result	Execution time	Memory
735363		ReLice	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	122 ms	48460 KiB

skyscraper

#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 (stderr)

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 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43