Submission #1138623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138623		huydarwin	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	51 ms	65360 KiB

skyscraper

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ii pii
#define fi first
#define sc second
#define ll long long
#define pll pair<ll,ll>
#define lli pair<ll,int>
#define ill pair<int,ll>
#define inf 2000000000
#define INF inf
#define endl "\n"
#define pb push_back
#define eb emplace_back
#define llinf (ll)1e18
#define LLINF llinf
#define maxn 30005
#define task "jakarta"

using namespace std;

int n,m;
ll b[maxn],p[maxn];
vector<ill> adj[maxn];
ll d[maxn];

void di(){
    for(int i=2;i<=m;i++) d[i]=llinf;
    set<lli> q;
    q.insert({0,1});
    while(!q.empty()){
        int u=q.begin()->sc;
        q.erase(q.begin());
        for(auto node: adj[u]){
            int v=node.fi; ll w=node.sc;
            if(d[v]>d[u]+w){
                if(d[v]!=llinf) q.erase({d[v],v});
                d[v]=d[u]+w;
                q.insert({d[v],v});
            }
        }
    }
}

void sub1(){
    for(int i=1;i<=m;i++) for(int j=1;j<=m;j++){
        if(i==j) continue;
        if(abs(b[i]-b[j])%p[i]==0){
            adj[i].eb(j, abs(b[i]-b[j])/p[i]);
        }
    }
    di();
    if(d[2]==llinf) cout<<-1<<endl;
    else cout<<d[2]<<endl;
}

int main(){
    if (fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }

    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>b[i]>>p[i];
    if(m<=2000) sub1();
    else cout<<-1<<endl;

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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