oj.uz

Submission #49029

# Submission time Handle Problem Language Result Execution time Memory
49029 2018-05-21T12:19:50 Z someone_aa Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 3 ms 876 KB 
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int maxn = 3100;
int dist[maxn][maxn];
bool visited[maxn][maxn];
int st[30100], p[30100], n, m;

set<int>ps[maxn];

int main() {
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        cin>>st[i]>>p[i];
        ps[st[i]].insert(p[i]);
    }

    queue<pair<int,int> > q;
    q.push(mp(st[0], p[0]));
    visited[st[0]][0] = true;

    while(!q.empty()) {
        int currx = q.front().first;
        int currc = q.front().second;
        q.pop();

        if(currx == st[1]) {
            cout<<dist[currx][currx]<<"\n";
            return 0;
        }

        if(currx - currc >= 0 && !visited[currx-currc][currc]) {
            visited[currx-currc][currc] = true;
            dist[currx-currc][currc] = dist[currx][currc] + 1;
            q.push(mp(currx-currc, currc));
        }

        if(currx + currc < n && !visited[currx+currc][currc]) {
            visited[currx+currc][currc] = true;
            dist[currx+currc][currc] = dist[currx][currc] + 1;
            q.push(mp(currx+currc, currc));
        }

        for(int i: ps[currx]) {
            if(currx - i >= 0 && !visited[currx-i][i]) {
                visited[currx-i][i] = true;
                dist[currx-i][i] = dist[currx][currc] + 1;
                q.push(mp(currx-i, i));
            }
            if(currx + i < n && !visited[currx+i][i]) {
                visited[currx+i][i] = true;
                dist[currx+i][i] = dist[currx][currc] + 1;
                q.push(mp(currx+i, i));
            }
        }
    }
    cout<<-1<<"\n";
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Incorrect 2 ms 632 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Incorrect 2 ms 760 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 788 KB Output is correct
5 Incorrect 3 ms 788 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 788 KB Output is correct
2 Correct 2 ms 788 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Incorrect 2 ms 876 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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