Submission #1028669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028669		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1067 ms	6352 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

const int N = 30010, M = 30010;
int n, m, b[M], p[M], dist[N];
bool mark[N];
map<pair<int, int>, bool> seen;
vector<int> vec[N];

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i ++){
        cin >> b[i] >> p[i];
        vec[b[i]].push_back(p[i]);
    }
    for (int i = 0; i < n; i ++){
        sort(vec[i].begin(), vec[i].end());
        vec[i].resize(unique(vec[i].begin(), vec[i].end()) - vec[i].begin());
    }

    memset(dist, 63, sizeof dist);
    dist[b[0]] = 0;

    for (int ii = 0; ii < n; ii ++){
        int v = -1;
        for (int j = 0; j < n; j ++)
            if (!mark[j] and (v == -1 or dist[v] > dist[j]))
                v = j;

        if (v == b[1]) break;

        mark[v] = 1;
        for (int d : vec[v]){
            if (seen.find({v, d}) != seen.end()) continue;

            for (int i = 1; v + d * i < n and dist[v] + i < dist[b[1]]; i ++){
                if (seen.find({v + d * i, d}) != seen.end()) break;

                if (dist[v + d * i] > dist[v] + i){
                    dist[v + d * i] = dist[v] + i;
                    seen[{v + d * i, d}] = 1;
                }
            }

            for (int i = 1; v - d * i >= 0 and dist[v] + i < dist[b[1]]; i ++){
                if (seen.find({v - d * i, d}) != seen.end()) break;

                if (dist[v - d * i] > dist[v] + i){
                    dist[v - d * i] = dist[v] + i;
                    seen[{v - d * i, d}] = 1;
                }
            }
        }
        
    }

    if (dist[b[1]] > 1e9)
        dist[b[1]] = -1;
    cout << dist[b[1]] << endl;
}

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