oj.uz

Submission #14402

# Submission time Handle Problem Language Result Execution time Memory
14402 2015-05-14T05:42:24 Z gs14004 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 12 ms 14892 KB 
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;

int m, n;

vector<int> vertex;
vector<int> dummy[30005];
vector<int> dx[30005];

bool r_dir[30005][180], l_dir[30005][180];

vector<int> graph[30005];
vector<int> graph0, graph1;
vector<bool> vis;

queue<int> pq[2];

inline int oldpi(int i, int j){
    return n * j + i;
}

inline int oldpi_first(int p){
    return (p % n + n) % n;
}

inline int oldpi_second(int p){
    return (p - oldpi_first(p)) / n;
}

int dijkstra(int st, int ed){
    pq[0].push(st);
    int dist = 0;
    while (1) {
        if(pq[dist%2].empty()) break;
        while (!pq[dist%2].empty()) {
            int qf = pq[dist%2].front();
            pq[dist%2].pop();
            if(qf == ed){
                return dist;
            }
            if(vis[qf]) continue;
            vis[qf] = 1;
            for (auto &i : graph[qf]){
                if(!vis[i]){
                    pq[dist%2].push(i);
                }
            }
            if(graph0[qf] != 0){
                pq[dist%2].push(graph0[qf]);
            }
            if(graph1[qf] != 0){
                pq[(dist+1)%2].push(graph1[qf]);
            }
        }
        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 < 180){
            r_dir[x][y] = 1;
            l_dir[x][y] = 1;
        }
        else{
            for (int j=0; j * y + x < n; j++) {
                dx[j * y + x].push_back(y);
            }
            for (int j=0; j * y + x >= 0; j--) {
                dx[j * y + x].push_back(-y);
            }
        }
        dummy[x].push_back(y);
    }
    for (int i=1; i<180; 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]){
                dx[j].push_back(i);
            }
            if(l_dir[j][i]){
                dx[j].push_back(-i);
            }
        }
    }
    for (int i=0; i<n; i++) {
        sort(dx[i].begin(),dx[i].end());
        dx[i].resize(unique(dx[i].begin(),dx[i].end()) - dx[i].begin());
        for (auto &j : dx[i]){
            vertex.push_back(oldpi(i,j));
        }
    }
    sort(vertex.begin(),vertex.end());
    graph0.resize(n + vertex.size());
    graph1.resize(n + vertex.size());
    vis.resize(n + vertex.size());
    for (int i=0; i<n; i++) {
        for(auto &j : dummy[i]){
            int pos = (int)(lower_bound(vertex.begin(),vertex.end(),oldpi(i,j)) - vertex.begin());
            if(pos != vertex.size() && vertex[pos] == oldpi(i,j)){
                graph[i].push_back(pos + n);
            }
            pos = (int)(lower_bound(vertex.begin(),vertex.end(),oldpi(i,-j)) - vertex.begin());
            if(pos != vertex.size() && vertex[pos] == oldpi(i,-j)){
                graph[i].push_back(pos + n);
            }
        }
    }
    for (int i=0; i<vertex.size(); i++){
        int tmp = vertex[i];
        graph0[i+n] = oldpi_first(vertex[i]);
        if(oldpi_first(tmp) + oldpi_second(tmp) < 0 || oldpi_first(tmp) + oldpi_second(tmp) >= n)
            continue;
        
        tmp = oldpi(oldpi_first(tmp) + oldpi_second(tmp),oldpi_second(tmp));
        int np = (int)(lower_bound(vertex.begin(),vertex.end(),tmp) - vertex.begin());
        if(np == vertex.size() || vertex[np] != tmp) continue;
        graph1[i+n] = np + n;
    }
    printf("%d\n",dijkstra(st,ed));
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14248 KB Output is correct
2 Correct 0 ms 14248 KB Output is correct
3 Correct 0 ms 14248 KB Output is correct
4 Correct 0 ms 14248 KB Output is correct
5 Correct 0 ms 14248 KB Output is correct
6 Correct 0 ms 14248 KB Output is correct
7 Correct 0 ms 14248 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14248 KB Output is correct
2 Correct 0 ms 14248 KB Output is correct
3 Correct 0 ms 14248 KB Output is correct
4 Correct 0 ms 14248 KB Output is correct
5 Correct 0 ms 14248 KB Output is correct
6 Correct 0 ms 14248 KB Output is correct
7 Correct 0 ms 14248 KB Output is correct
8 Correct 2 ms 14248 KB Output is correct
9 Correct 0 ms 14248 KB Output is correct
10 Correct 0 ms 14248 KB Output is correct
11 Correct 0 ms 14380 KB Output is correct
12 Correct 0 ms 14248 KB Output is correct
13 Correct 0 ms 14248 KB Output is correct
14 Correct 4 ms 14408 KB Output is correct
15 Correct 4 ms 14408 KB Output is correct

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14248 KB Output is correct
2 Correct 0 ms 14248 KB Output is correct
3 Correct 1 ms 14248 KB Output is correct
4 Correct 0 ms 14248 KB Output is correct
5 Correct 0 ms 14248 KB Output is correct
6 Correct 0 ms 14248 KB Output is correct
7 Correct 0 ms 14248 KB Output is correct
8 Correct 2 ms 14248 KB Output is correct
9 Correct 0 ms 14248 KB Output is correct
10 Correct 2 ms 14248 KB Output is correct
11 Correct 2 ms 14380 KB Output is correct
12 Correct 2 ms 14248 KB Output is correct
13 Correct 0 ms 14248 KB Output is correct
14 Correct 2 ms 14408 KB Output is correct
15 Correct 4 ms 14408 KB Output is correct
16 Correct 3 ms 14388 KB Output is correct
17 Correct 9 ms 14764 KB Output is correct
18 Correct 6 ms 14388 KB Output is correct
19 Correct 7 ms 14396 KB Output is correct
20 Correct 7 ms 14380 KB Output is correct
21 Correct 4 ms 14248 KB Output is correct
22 Correct 6 ms 14408 KB Output is correct
23 Correct 8 ms 14384 KB Output is correct
24 Correct 8 ms 14552 KB Output is correct
25 Correct 12 ms 14528 KB Output is correct
26 Correct 5 ms 14548 KB Output is correct
27 Correct 10 ms 14404 KB Output is correct
28 Incorrect 9 ms 14892 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14248 KB Output is correct
2 Correct 0 ms 14248 KB Output is correct
3 Correct 0 ms 14248 KB Output is correct
4 Correct 0 ms 14248 KB Output is correct
5 Correct 0 ms 14248 KB Output is correct
6 Correct 0 ms 14248 KB Output is correct
7 Correct 0 ms 14248 KB Output is correct
8 Correct 0 ms 14248 KB Output is correct
9 Correct 0 ms 14248 KB Output is correct
10 Correct 0 ms 14248 KB Output is correct
11 Correct 2 ms 14380 KB Output is correct
12 Correct 0 ms 14248 KB Output is correct
13 Correct 0 ms 14248 KB Output is correct
14 Correct 4 ms 14408 KB Output is correct
15 Correct 4 ms 14408 KB Output is correct
16 Correct 3 ms 14388 KB Output is correct
17 Correct 4 ms 14764 KB Output is correct
18 Correct 9 ms 14388 KB Output is correct
19 Correct 7 ms 14396 KB Output is correct
20 Correct 7 ms 14380 KB Output is correct
21 Correct 0 ms 14248 KB Output is correct
22 Correct 3 ms 14408 KB Output is correct
23 Correct 6 ms 14384 KB Output is correct
24 Correct 11 ms 14552 KB Output is correct
25 Correct 10 ms 14528 KB Output is correct
26 Correct 7 ms 14548 KB Output is correct
27 Correct 6 ms 14404 KB Output is correct
28 Incorrect 11 ms 14892 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14248 KB Output is correct
2 Correct 0 ms 14248 KB Output is correct
3 Correct 0 ms 14248 KB Output is correct
4 Correct 0 ms 14248 KB Output is correct
5 Correct 0 ms 14248 KB Output is correct
6 Correct 0 ms 14248 KB Output is correct
7 Correct 0 ms 14248 KB Output is correct
8 Correct 0 ms 14248 KB Output is correct
9 Correct 0 ms 14248 KB Output is correct
10 Correct 3 ms 14248 KB Output is correct
11 Correct 4 ms 14380 KB Output is correct
12 Correct 0 ms 14248 KB Output is correct
13 Correct 0 ms 14248 KB Output is correct
14 Correct 3 ms 14408 KB Output is correct
15 Correct 3 ms 14408 KB Output is correct
16 Correct 0 ms 14388 KB Output is correct
17 Correct 8 ms 14764 KB Output is correct
18 Correct 6 ms 14388 KB Output is correct
19 Correct 7 ms 14396 KB Output is correct
20 Correct 7 ms 14380 KB Output is correct
21 Correct 3 ms 14248 KB Output is correct
22 Correct 4 ms 14408 KB Output is correct
23 Correct 5 ms 14384 KB Output is correct
24 Correct 11 ms 14552 KB Output is correct
25 Correct 11 ms 14528 KB Output is correct
26 Correct 10 ms 14548 KB Output is correct
27 Correct 6 ms 14404 KB Output is correct
28 Incorrect 9 ms 14892 KB Output isn't correct
29 Halted 0 ms 0 KB -