Submission #1195548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195548		cpdreamer	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	22 / 100	1104 ms	321944 KiB

skyscraper

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define V vector
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define P pair
#define F first
#define S second
const ll MOD=(ll)1e9+7;
void file() {
    freopen("input.txt.txt", "r", stdin);
    freopen("output.txt.txt", "w", stdout);
}
V<P<int,int>>adj[(int)4e6+1];
V<bool>processed((int)4e6+1,false);
V<int>dis(4e6 + 1, 1e8);
void  bfs(int n,int x){
    priority_queue<P<int,int>>q;
    dis[x] = 0;
    q.push({0,x});
    while (!q.empty()) {
        int a = q.top().second; q.pop();
        if (processed[a]) continue;
        processed[a] = true;
        for (auto u : adj[a]) {
            int b = u.first, w = u.second;
            if (dis[a] + w < dis[b]) {
                dis[b] = dis[a] + w;
                q.push({-dis[b], b});
            }
        }
    }
}
void solve() {
    int n;
    cin>>n;
    int m;
    cin>>m;
    V<P<int,int>>d(m);
    for(int i=0;i<m;i++){
        cin>>d[i].F>>d[i].S;
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            int c=i*n;
            if(j+d[i].S<n){
                adj[j+c].pb({j+d[i].S+c,1});
                adj[j+d[i].S+c].pb({j+c,1});
            }
        }
    }
    for(int i=0;i<m;i++){
        int c=i*n;
        for(int j=0;j<m;j++){
            int c1=j*n;
            if(i==j)continue;
            adj[d[i].F+c1].pb({d[i].F+c,0});
        }
    }
    int ans=INT_MAX;
    bfs(n,d[0].F);
    for(int i=0;i<m;i++){
        ans=min(ans,dis[d[1].F+i*n]);
    }
    if(ans>=1e8)
        cout<<-1<<endl;
    else {
        cout << ans << endl;
    }
}

int main(){
  //  file();
    solve();
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void file()':
skyscraper.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("input.txt.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("output.txt.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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