Submission #674531

#	Time	Username	Problem	Language	Result	Execution time	Memory
674531		AmirH	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	177 ms	68008 KiB

skyscraper

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<bitset>
#include<queue>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<unordered_map>
#include<list>
#include<utility>
#include<stack>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
#define cl clear
#define F  first
#define S  second
#define pb push_back
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int MAX_N = 3e4 + 25;
const ll INF = 1e18;
const int inf = 1e9;
const int mod = 1e9 + 7;
void free() {
    #ifndef ONLINE_JUDGE
        freopen("inputi.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
}
int n, m;
vector<pii> v;
set<pii> s[MAX_N];
vector<pii> adj[MAX_N];

int dij(int start, int end) {
    vector<int> dist(n, inf);
    dist[start] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    while(!pq.empty()) {
        auto tren = pq.top();
        pq.pop();
        if(dist[tren.second] != tren.first) 
                continue;
        for(auto e : adj[tren.second]) {
            if(dist[e.first] > dist[tren.second] + e.second) {
                dist[e.first] = dist[tren.second] + e.second;
                pq.push({dist[e.first], e.first});
            }
        }
    }
    return dist[end];
}
int main() {
    faster; //free();
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        v.pb({x, y});
    }
    for(auto i : v) {
        s[i.first].insert(i);
    }
    for(int i = 0; i < n; i++) {
        for(auto z : s[i]) {
            if(z.second == 0) 
                continue;
            for(int j = 1; j < n; j++) {
                int nx = j * z.second + i;
                if(nx >= n) 
                    break;
                adj[i].push_back({nx, j});
                if(s[nx].count({nx, z.second})) 
                    break;
            }
            for(int j = 1; j < n; ++j) {
                int nx = -j * z.second + i;
                if(nx < 0) 
                    break;
                adj[i].push_back({nx, j});
                if(s[nx].count({nx, z.second})) 
                    break;
            }
        }
    }
    int ans = dij(v[0].first, v[1].first);
    if(ans >= inf)
        cout << -1;
    else
        cout << ans;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void free()':
skyscraper.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("inputi.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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