oj.uz

Submission #14433

# Submission time Handle Problem Language Result Execution time Memory
14433 2015-05-14T11:42:28 Z gs14004 Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 27 ms 35644 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];
queue<int> pq[30005];

int dijkstra(int st, int ed){
    pq[0].push(st);
    int dist = 0, cnt = 1;
    while (cnt) {
        while (!pq[dist].empty()) {
            int t = pq[dist].front();
            pq[dist].pop();
            cnt--;
            if(t == ed){
                return dist;
            }
            if(vis[t]) continue;
            vis[t] = 1;
            if(t < n){
                for (auto &i : graph[t]){
                    if(!vis[i.second] && i.first + dist <= n)
                        pq[i.first + dist].push(i.second), cnt++;
                }
            }
            int px = t % n;
            int py = t / n;
            if(r_dir[px][py] && px + py < n){
                if(!vis[py * n + px + py]){
                    cnt++;
                    pq[dist + 1].push(py * n + px + py);
                }
            }
            if(l_dir[px][py] && px - py >= 0){
                if(!vis[py * n + px - py]){
                    cnt++;
                    pq[dist + 1].push(py * n + px - py);
                }
            }
            if(py){
                if(!vis[px]){
                    cnt++;
                    pq[dist].push(px);
                }
            }
        }
        dist++;
    }
    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<B; 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];
        }
    }
    printf("%d",dijkstra(st,ed));
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35508 KB Output is correct
2 Correct 0 ms 35508 KB Output is correct
3 Correct 24 ms 35508 KB Output is correct
4 Correct 24 ms 35508 KB Output is correct
5 Correct 12 ms 35508 KB Output is correct
6 Correct 5 ms 35508 KB Output is correct
7 Correct 15 ms 35508 KB Output is correct

Subtask #2
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 35508 KB Output is correct
2 Correct 8 ms 35508 KB Output is correct
3 Correct 9 ms 35508 KB Output is correct
4 Correct 12 ms 35508 KB Output is correct
5 Correct 16 ms 35508 KB Output is correct
6 Correct 19 ms 35508 KB Output is correct
7 Correct 8 ms 35508 KB Output is correct
8 Correct 11 ms 35508 KB Output is correct
9 Correct 12 ms 35508 KB Output is correct
10 Correct 20 ms 35508 KB Output is correct
11 Correct 22 ms 35640 KB Output is correct
12 Incorrect 13 ms 35644 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35508 KB Output is correct
2 Correct 15 ms 35508 KB Output is correct
3 Correct 0 ms 35508 KB Output is correct
4 Correct 12 ms 35508 KB Output is correct
5 Correct 0 ms 35508 KB Output is correct
6 Correct 11 ms 35508 KB Output is correct
7 Correct 11 ms 35508 KB Output is correct
8 Correct 14 ms 35508 KB Output is correct
9 Correct 14 ms 35508 KB Output is correct
10 Correct 16 ms 35508 KB Output is correct
11 Correct 8 ms 35640 KB Output is correct
12 Incorrect 11 ms 35644 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35508 KB Output is correct
2 Correct 6 ms 35508 KB Output is correct
3 Correct 8 ms 35508 KB Output is correct
4 Correct 14 ms 35508 KB Output is correct
5 Correct 14 ms 35508 KB Output is correct
6 Correct 15 ms 35508 KB Output is correct
7 Correct 26 ms 35508 KB Output is correct
8 Correct 11 ms 35508 KB Output is correct
9 Correct 12 ms 35508 KB Output is correct
10 Correct 12 ms 35508 KB Output is correct
11 Correct 17 ms 35640 KB Output is correct
12 Incorrect 3 ms 35644 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 35508 KB Output is correct
2 Correct 12 ms 35508 KB Output is correct
3 Correct 8 ms 35508 KB Output is correct
4 Correct 18 ms 35508 KB Output is correct
5 Correct 8 ms 35508 KB Output is correct
6 Correct 19 ms 35508 KB Output is correct
7 Correct 8 ms 35508 KB Output is correct
8 Correct 17 ms 35508 KB Output is correct
9 Correct 12 ms 35508 KB Output is correct
10 Correct 26 ms 35508 KB Output is correct
11 Correct 27 ms 35640 KB Output is correct
12 Incorrect 23 ms 35644 KB Output isn't correct
13 Halted 0 ms 0 KB -