Submission #112273

# Submission time Handle Problem Language Result Execution time Memory
112273 2019-05-18T12:16:35 Z dolphingarlic Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
8 ms 7808 KB
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Doge {
    int jumps, pos, size, direction;
};

vector<pair<int, int>> sky[300001];
bool visited[300001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    fill(visited, visited + 300001, false);
    int n, m;
    cin >> n >> m;
    int size, pos;
    FOR(i, 0, m) {
        int a, b;
        cin >> a >> b;
        sky[a].push_back({i, b});
        if (i == 0) size = b, pos = a;
    }

    queue<Doge> q;
    q.push({0, pos, size, 1});
    while (!q.empty()) {
        Doge curr = q.front();
        q.pop();
        bool push = true;
        // cout << curr.jumps << ' ' << curr.pos << ' ' << curr.size << ' ' << curr.direction << '\n';

        if (curr.direction) {
            if (curr.pos + curr.size < n) {
                if (!visited[curr.pos + curr.size]) {
                    visited[curr.pos + curr.size] = true;
                    for (auto& i : sky[curr.pos + curr.size]) {
                        if (i.first == 1) return cout << curr.jumps + 1 << '\n', 0;
                        if (i.second != curr.size) {
                            q.push({curr.jumps + 1, curr.pos + curr.size, i.second, 1});
                            q.push({curr.jumps + 1, curr.pos + curr.size, i.second, 0});
                        }
                    }
                } else {
                    for (auto& i : sky[curr.pos + curr.size]) {
                        if (i.second == curr.size) {
                            push = false;
                        }
                    }
                }
            }
            if (push && curr.pos + curr.size < n) q.push({curr.jumps + 1, curr.pos + curr.size, curr.size, 1});
        } else {
            if (curr.pos - curr.size > -1) {
                if (!visited[curr.pos - curr.size]) {
                    visited[curr.pos - curr.size] = true;
                    for (auto& i : sky[curr.pos - curr.size]) {
                        if (i.first == 1) return cout << curr.jumps + 1 << '\n', 0;
                        if (i.second != curr.size) {
                            q.push({curr.jumps + 1, curr.pos - curr.size, i.second, 1});
                            q.push({curr.jumps + 1, curr.pos - curr.size, i.second, 0});
                        }
                    }
                } else {
                    for (auto& i : sky[curr.pos - curr.size]) {
                        if (i.second == curr.size) {
                            push = false;
                        }
                    }
                }
            }
            if (push && curr.pos - curr.size > -1) q.push({curr.jumps + 1, curr.pos - curr.size, curr.size, 0});
        }
    }
    cout << "-1\n";
    return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:29:11: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
     q.push({0, pos, size, 1});
     ~~~~~~^~~~~~~~~~~~~~~~~~~
skyscraper.cpp:29:11: warning: 'size' may be used uninitialized in this function [-Wmaybe-uninitialized]
# Verdict Execution time Memory Grader output
1 Correct 8 ms 7680 KB Output is correct
2 Incorrect 7 ms 7680 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 7680 KB Output is correct
2 Incorrect 7 ms 7680 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 7680 KB Output is correct
2 Incorrect 8 ms 7808 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 7680 KB Output is correct
2 Incorrect 8 ms 7680 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 7680 KB Output is correct
2 Incorrect 8 ms 7760 KB Output isn't correct
3 Halted 0 ms 0 KB -