Submission #107938

#	Time	Username	Problem	Language	Result	Execution time	Memory
107938		patrikpavic2	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1060 ms	44116 KiB

skyscraper

#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <deque>
#include <unordered_map>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef set < int > si;

const int N = 3e4 + 500;
const int M = 105;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int LOG = 18;
const int OFF = (1 << LOG);
const double EPS = 1e-9;
const double PI = 3.1415926535;

unordered_map <int, int> dis[N];
int en, bio[N], x[N], y[N];
int n, m;
vector < int > pot[N];

deque < pii > q;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0;i < m;i++){
        scanf("%d%d", x + i, y + i);
        pot[x[i]].PB(y[i]);
    }
    dis[x[0]][y[0]] = 0;
    q.push_back({x[0], y[0]});
    while(!q.empty()){
        int cur = q.front().X;
        int sk = q.front().Y;
        //printf("%d %d = %d\n", cur, sk, dis[cur][sk]);
        q.pop_front();
        if(!bio[cur]){
            for(int x : pot[cur]){
                if((dis[cur].count(x) == 0 || dis[cur][sk] < dis[cur][x]))
                    q.push_front({cur, x}), dis[cur][x] = dis[cur][sk];
            }
        }
        bio[cur] = 1;
        if(cur - sk >= 0 && (dis[cur - sk].count(sk) == 0 || dis[cur - sk][sk] > 1 + dis[cur][sk]))
            q.push_back({cur - sk, sk}), dis[cur - sk][sk] = 1 + dis[cur][sk];
        if(cur + sk < n && (dis[cur + sk].count(sk) == 0 || dis[cur + sk][sk] > 1 + dis[cur][sk]))
            q.push_back({cur + sk, sk}), dis[cur + sk][sk] = 1 + dis[cur][sk];
    }
    int ans = INF;
    for(int i = 0;i <= n;i++) if(dis[x[1]].count(i)) ans = min(ans, dis[x[1]][i]);
    if(ans == INF) printf("-1\n");
    else printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", x + i, y + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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