Submission #284621

#	Time	Username	Problem	Language	Result	Execution time	Memory
284621		doowey	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	958 ms	27128 KiB

skyscraper

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 30010;
const int MX = 1e6;
const int inf = (int)1e9;
int dist[N];
vector<int> id[MX];
vector<int> q[N];

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    int st = -1, en = -1;
    int xi, yi;
    for(int i = 0 ; i < n; i ++ ){
        dist[i] = inf;
    }
    for(int i = 0 ; i < m; i ++ ){
        cin >> xi >> yi;
        q[xi].push_back(yi);
        if(i == 0){
            st = xi;
        }
        else if(i == 1){
            en = xi;
        }
    }
    id[0].push_back(st);
    dist[st] = 0;
    for(int i = 0 ; i < MX; i ++ ){
        if(id[i].empty()) continue;
        for(auto x : id[i]){ // this just adds +n so its fine
            if(x == en){
                cout << i << "\n";
                return 0;
            }
        }
        for(auto x : id[i]){
            if(dist[x] != i) continue;
            for(auto y : q[x]){
                for(int f = 1; x + y * f < n && i + f < MX; f ++ ){
                    if(dist[x + y * f] > i + f){
                        dist[x + y * f] = i + f;
                        id[i + f].push_back(x + y * f);
                    }
                }
                for(int f = 1; x - y * f >= 0 && i + f < MX; f ++ ){
                    if(dist[x - y * f] > i + f){
                        dist[x - y * f] = i + f;
                        id[i + f].push_back(x - y * f);
                    }
                }
            }
        }
    }
    cout << "-1\n";
    return 0;
}

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