oj.uz

Submission #49026

# Submission time Handle Problem Language Result Execution time Memory
49026 2018-05-21T12:11:59 Z someone_aa Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 3 ms 740 KB 
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int maxn = 2100;
int dist[maxn][maxn];
bool visited[maxn][maxn];
int st[maxn], p[maxn], 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;
    visited[st[0]][p[0]]=true;
    
    while(!q.empty()) {
        int currx = q.front().first;
        int currc = q.front().second;
        q.pop();

        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));
            }
        }
    }
    int result = INT_MAX;
    for(int i=0;i<maxn;i++) {
        if(visited[st[1]][i]) result = min(result, dist[st[1]][i]);
    }
    cout<<result<<"\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 2 ms 616 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Incorrect 3 ms 616 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 43.0

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