Submission #107946

#	Time	Username	Problem	Language	Result	Execution time	Memory
107946		patrikpavic2	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1081 ms	125688 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>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#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 = 205;
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;

int dis1[N][M];
gp_hash_table <int, int> dis2[N];
int en, bio[N], x[N], y[N];
int n, m;
vector < int > pot[N];

int dis(int a,int b){
    if(b < M) return dis1[a][b];
    return dis2[a][b];
}

void postavi(int a,int b,int c){
    if(b < M) dis1[a][b] = c;
    else dis2[a][b] = c;
}

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

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:55: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:57: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