oj.uz

Submission #434183

# Submission time Handle Problem Language Result Execution time Memory
434183 2021-06-20T17:11:37 Z KienTranluvChaeng Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 1 ms 344 KB 
#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 (d[doge[1]] != 1e18) break;
        if ((get<1>(u) - doge[1]) % get<2>(u) == 0){
            int cnt = 0, v = get<1>(u);
            while (v < doge[1]){
                v += get<2>(u);
                cnt += 1;
            }
            while (v > doge[1]){
                v -= get<2>(u);
                cnt += 1;
            }
            d[doge[1]] = cnt + get<0>(u);
            break;
        }
        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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Incorrect 1 ms 324 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Halted 0 ms 0 KB -