oj.uz

Submission #14405

# Submission time Handle Problem Language Result Execution time Memory
14405 2015-05-14T06:10:31 Z gs14004 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 14 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;
            if(qf < n){
                for (auto &i : graph[qf]){
                    if(!vis[i]){
                        pq[dist%2].push(i);
                    }
                }
            }
            if(qf >= n && graph0[qf] != 0 && !vis[graph0[qf]]){
                pq[dist%2].push(graph0[qf]);
            }
            if(qf >= n && graph1[qf] != 0 && !vis[graph1[qf]]){
                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 2 ms 14248 KB Output is correct
6 Correct 2 ms 14248 KB Output is correct
7 Correct 0 ms 14248 KB Output is correct
8 Correct 1 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 0 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 4 ms 14408 KB Output is correct
15 Correct 3 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 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 3 ms 14380 KB Output is correct
12 Correct 3 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 0 ms 14408 KB Output is correct
16 Correct 3 ms 14388 KB Output is correct
17 Correct 6 ms 14764 KB Output is correct
18 Correct 6 ms 14388 KB Output is correct
19 Correct 9 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 4 ms 14408 KB Output is correct
23 Correct 4 ms 14384 KB Output is correct
24 Correct 8 ms 14552 KB Output is correct
25 Correct 7 ms 14528 KB Output is correct
26 Correct 5 ms 14548 KB Output is correct
27 Correct 7 ms 14404 KB Output is correct
28 Incorrect 11 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 2 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 4 ms 14380 KB Output is correct
12 Correct 0 ms 14248 KB Output is correct
13 Correct 2 ms 14248 KB Output is correct
14 Correct 0 ms 14408 KB Output is correct
15 Correct 4 ms 14408 KB Output is correct
16 Correct 0 ms 14388 KB Output is correct
17 Correct 9 ms 14764 KB Output is correct
18 Correct 4 ms 14388 KB Output is correct
19 Correct 4 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 6 ms 14408 KB Output is correct
23 Correct 8 ms 14384 KB Output is correct
24 Correct 7 ms 14552 KB Output is correct
25 Correct 10 ms 14528 KB Output is correct
26 Correct 9 ms 14548 KB Output is correct
27 Correct 7 ms 14404 KB Output is correct
28 Incorrect 14 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 2 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 4 ms 14380 KB Output is correct
12 Correct 2 ms 14248 KB Output is correct
13 Correct 2 ms 14248 KB Output is correct
14 Correct 3 ms 14408 KB Output is correct
15 Correct 0 ms 14408 KB Output is correct
16 Correct 2 ms 14388 KB Output is correct
17 Correct 6 ms 14764 KB Output is correct
18 Correct 4 ms 14388 KB Output is correct
19 Correct 7 ms 14396 KB Output is correct
20 Correct 6 ms 14380 KB Output is correct
21 Correct 0 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 11 ms 14552 KB Output is correct
25 Correct 7 ms 14528 KB Output is correct
26 Correct 4 ms 14548 KB Output is correct
27 Correct 7 ms 14404 KB Output is correct
28 Incorrect 13 ms 14892 KB Output isn't correct
29 Halted 0 ms 0 KB -