Submission #387948

#	Time	Username	Problem	Language	Result	Execution time	Memory
387948		cpp219	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	525 ms	262148 KiB

skyscraper

#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 3e4 + 6;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
vector<LL> v;
struct doge{
    ll pos,p,id;
};
doge a[N];
ll n,m,d[N];
map<LL,ll> mp;
vector<LL> g[N];

void Dij(){
    fill(d,d + N - 1,inf);
    priority_queue<LL,vector<LL>,greater<LL>> pq; pq.push({0,a[1].pos}); d[a[1].pos] = 0;
    while(!pq.empty()){
        LL t = pq.top(); pq.pop();
        ll u = t.sc;
        for (auto i : g[u]){
            ll v = i.fs,L = i.sc;
            if (d[v] > d[u] + L) d[v] = d[u] + L,pq.push({d[v],v});
        }
    }
    //for (auto i : g[1]) cout<<i.fs<<"x "; exit(0);
    //cout<<d[2]; exit(0);
    if (d[a[2].pos] != inf) cout<<d[a[2].pos];
    else cout<<-1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>m;
    for (ll i = 1;i <= m;i++) cin>>a[i].pos>>a[i].p,a[i].pos++;
    for (ll i = 1;i <= m;i++){
        LL now = {a[i].pos,a[i].p};
        if (mp[now]) continue; mp[now] = 1;
        ll cost = 1;
        for (ll j = now.fs + a[i].p;j <= n;j += a[i].p){
            //if (mp[{j,now.sc}]) break;
            //mp[{j,now.sc}] = 1; //cout<<j<<" ";
            g[now.fs].push_back({j,cost}),cost++;
        }
        cost = 1; //return 0;
        for (ll j = now.fs - a[i].p;j > 0;j -= a[i].p){
            //if (mp[{j,now.sc}]) break;
            //mp[{j,now.sc}] = 1;
            g[now.fs].push_back({j,cost}),cost++;
            //if (now.fs == 5) cout<<j<<" x ";
        }
    }
    Dij();
}

Compilation message (stderr)

skyscraper.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "Ofast"
      | 
skyscraper.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:53:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   53 |         if (mp[now]) continue; mp[now] = 1;
      |         ^~
skyscraper.cpp:53:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   53 |         if (mp[now]) continue; mp[now] = 1;
      |                                ^~
skyscraper.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   46 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43