Submission #434185

#	Time	Username	Problem	Language	Result	Execution time	Memory
434185		KienTranluvChaeng	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	2 ms	460 KiB

skyscraper

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int O = 3e5 + 5;

int n, m, doge[O], p[O], d[O], vis[O];

vector <vector <int>> g;

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m; g.resize(n);
    for (int i = 0; i < m; ++ i){
        cin >> doge[i] >> p[i];
        g[doge[i]].push_back(p[i]);
    }

    deque <tuple <int, int, int>> q;
    for (int i = 0; i < n; ++ i) d[i] = 1e18;
    d[doge[0]] = 0;
    for (int i : g[doge[0]]) q.push_back(make_tuple(0, doge[0], i)), q.push_back(make_tuple(0, doge[0], -i));
    while (q.size()){
        tuple <int, int, int> u = q.front(); q.pop_front();
        if ((get<1>(u) - doge[1]) % get<2>(u) == 0){
            d[doge[1]] = min(d[doge[1]], get<0>(u) + abs((get<1>(u) - doge[1]) / get<2>(u)));
            continue;
        }
        if (get<0>(u) != d[get<1>(u)]) break;
        int h = get<1>(u) + get<2>(u);
        if (h < n && h){
            if (d[h] > get<0>(u) + 1){
                d[h] = get<0>(u) + 1;
                for (int i : g[h]) q.push_back(make_tuple(d[h], h, i)), q.push_back(make_tuple(d[h], h, -i));
                q.push_back(make_tuple(d[h], h, get<2>(u)));
            }
        }
    }
    if (d[doge[1]] == 1e18) d[doge[1]] = -1;
    cout << d[doge[1]];
    return 0;
}

Compilation message (stderr)

skyscraper.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main(){
      | ^~~~

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