oj.uz

Submission #14411

# Submission time Handle Problem Language Result Execution time Memory
14411 2015-05-14T07:21:27 Z gs14004 Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 30 ms 119884 KB 
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> pi;
const int B = 150;

int m, n;

bool r_dir[30005][B], l_dir[30005][B];
bool vis[30005 * B];
vector<pi> graph[30005 * B];
priority_queue<pi,vector<pi>,greater<pi> > pq;

int dijkstra(int st, int ed){
    pq.push(pi(0,st));
    while (!pq.empty()) {
        pi t = pq.top();
        pq.pop();
        if(t.second == ed){
            return t.first;
        }
        if(vis[t.second]) continue;
        vis[t.second] = 1;
        for (auto &i : graph[t.second]){
            if(!vis[i.second]) pq.push(pi(i.first + t.first,i.second));
        }
    }
    return -1;
}

int main(){
    int st = 0, ed = 0;
    scanf("%d %d",&n,&m);
    for (int i=0; i<m; i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        if(i == 0){
            st = x;
        }
        else if(i == 1){
            ed = x;
        }
        if(y < B){
            r_dir[x][y] = 1;
            l_dir[x][y] = 1;
            graph[x].push_back(pi(0,x + n * y));
        }
        else{
            for (int j=1; x - j * y >= 0; j++) {
                graph[x].push_back(pi(j,x - j * y));
            }
            for (int j=1; x + j * y < n; j++) {
                graph[x].push_back(pi(j,x + j * y));
            }
        }
    }
    for (int i=1; i<3; i++) {
        for (int j=i; j<n; j++) {
            r_dir[j][i] |= r_dir[j - i][i];
        }
        for (int j=n-i-1; j>=0; j--) {
            l_dir[j][i] |= l_dir[j + i][i];
        }
        for (int j=0; j<n; j++) {
            if(r_dir[j][i] && j + i < n){
                graph[i * n + j].push_back(pi(1,i * n + j + i));
            }
            if(l_dir[j][i] && j - i >= 0){
                graph[i * n + j].push_back(pi(1,i * n + j - i));
            }
            graph[i * n + j].push_back(pi(0,j));
        }
    }
    printf("%d",dijkstra(st,ed));
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 119884 KB Output is correct
2 Correct 22 ms 119884 KB Output is correct
3 Correct 25 ms 119884 KB Output is correct
4 Correct 12 ms 119884 KB Output is correct
5 Correct 8 ms 119884 KB Output is correct
6 Incorrect 21 ms 119884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 119884 KB Output is correct
2 Correct 24 ms 119884 KB Output is correct
3 Correct 11 ms 119884 KB Output is correct
4 Correct 18 ms 119884 KB Output is correct
5 Correct 22 ms 119884 KB Output is correct
6 Incorrect 16 ms 119884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 119884 KB Output is correct
2 Correct 12 ms 119884 KB Output is correct
3 Correct 16 ms 119884 KB Output is correct
4 Correct 30 ms 119884 KB Output is correct
5 Correct 30 ms 119884 KB Output is correct
6 Incorrect 29 ms 119884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 119884 KB Output is correct
2 Correct 16 ms 119884 KB Output is correct
3 Correct 11 ms 119884 KB Output is correct
4 Correct 16 ms 119884 KB Output is correct
5 Correct 26 ms 119884 KB Output is correct
6 Incorrect 26 ms 119884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 119884 KB Output is correct
2 Correct 21 ms 119884 KB Output is correct
3 Correct 16 ms 119884 KB Output is correct
4 Correct 16 ms 119884 KB Output is correct
5 Correct 12 ms 119884 KB Output is correct
6 Incorrect 24 ms 119884 KB Output isn't correct
7 Halted 0 ms 0 KB -