oj.uz

Submission #14396

# Submission time Handle Problem Language Result Execution time Memory
14396 2015-05-14T03:32:07 Z gs14004 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 220 ms 262144 KB 
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> pi;

int m, n;

vector<pi> vertex;
vector<int> dummy[3005];

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

vector<vector<pi> > graph;
priority_queue<pi,vector<pi>,greater<pi> > pq;

bool vis[12300005];

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, ed;
    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 <= 100){
            r_dir[x][y] = 1;
            l_dir[x][y] = 1;
        }
        else{
            for (int j=0; j * (y) + x < n; j++) {
                vertex.push_back(pi(j * y + x,y));
            }
            for (int j=0; j * (y) + x >= 0; i--) {
                vertex.push_back(pi(j * y + x,-y));
            }
        }
        dummy[x].push_back(y);
    }
    for (int i=1; i<=100; 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]){
                vertex.push_back(pi(j,i));
            }
            if(l_dir[j][i]){
                vertex.push_back(pi(j,-i));
            }
        }
    }
    sort(vertex.begin(),vertex.end());
    vertex.resize(unique(vertex.begin(),vertex.end()) - vertex.begin());
    graph.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(),pi(i,j)) - vertex.begin());
            if(pos != vertex.size() && vertex[pos] == pi(i,j)){
                graph[i].push_back(pi(0,pos+n));
            }
            pos = (int)(lower_bound(vertex.begin(),vertex.end(),pi(i,-j)) - vertex.begin());
            if(pos != vertex.size() && vertex[pos] == pi(i,-j)){
                graph[i].push_back(pi(0,pos+n));
            }
        }
    }
    for (int i=0; i<vertex.size(); i++){
        pi tmp = vertex[i];
        tmp.first += tmp.second;
        int np = (int)(lower_bound(vertex.begin(),vertex.end(),tmp) - vertex.begin());
        graph[i+n].push_back(pi(0,vertex[i].first));
        if(np == vertex.size() || vertex[np] != tmp) continue;
        graph[i+n].push_back(pi(1,np + n));
    }
    printf("%d",dijkstra(st,ed));
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19820 KB Output is correct
2 Correct 0 ms 19820 KB Output is correct
3 Correct 0 ms 19820 KB Output is correct
4 Correct 0 ms 19820 KB Output is correct
5 Correct 0 ms 19820 KB Output is correct
6 Correct 0 ms 19820 KB Output is correct
7 Correct 0 ms 19820 KB Output is correct
8 Correct 0 ms 19820 KB Output is correct
9 Correct 0 ms 19820 KB Output is correct
10 Correct 2 ms 19952 KB Output is correct
11 Correct 4 ms 20256 KB Output is correct
12 Correct 0 ms 19820 KB Output is correct
13 Correct 0 ms 19820 KB Output is correct
14 Correct 5 ms 20288 KB Output is correct
15 Correct 5 ms 20292 KB Output is correct

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19820 KB Output is correct
2 Correct 0 ms 19820 KB Output is correct
3 Correct 0 ms 19820 KB Output is correct
4 Correct 0 ms 19820 KB Output is correct
5 Correct 0 ms 19820 KB Output is correct
6 Correct 0 ms 19820 KB Output is correct
7 Correct 0 ms 19820 KB Output is correct
8 Correct 0 ms 19820 KB Output is correct
9 Correct 0 ms 19820 KB Output is correct
10 Correct 0 ms 19952 KB Output is correct
11 Correct 2 ms 20256 KB Output is correct
12 Correct 1 ms 19820 KB Output is correct
13 Correct 1 ms 19820 KB Output is correct
14 Correct 5 ms 20288 KB Output is correct
15 Correct 4 ms 20292 KB Output is correct
16 Memory limit exceeded 207 ms 262144 KB Memory limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19820 KB Output is correct
2 Correct 0 ms 19820 KB Output is correct
3 Correct 0 ms 19820 KB Output is correct
4 Correct 0 ms 19820 KB Output is correct
5 Correct 0 ms 19820 KB Output is correct
6 Correct 0 ms 19820 KB Output is correct
7 Correct 0 ms 19820 KB Output is correct
8 Correct 0 ms 19820 KB Output is correct
9 Correct 0 ms 19820 KB Output is correct
10 Correct 0 ms 19952 KB Output is correct
11 Correct 4 ms 20256 KB Output is correct
12 Correct 1 ms 19820 KB Output is correct
13 Correct 0 ms 19820 KB Output is correct
14 Correct 2 ms 20288 KB Output is correct
15 Correct 5 ms 20292 KB Output is correct
16 Memory limit exceeded 210 ms 262144 KB Memory limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19820 KB Output is correct
2 Correct 0 ms 19820 KB Output is correct
3 Correct 0 ms 19820 KB Output is correct
4 Correct 0 ms 19820 KB Output is correct
5 Correct 0 ms 19820 KB Output is correct
6 Correct 0 ms 19820 KB Output is correct
7 Correct 0 ms 19820 KB Output is correct
8 Correct 0 ms 19820 KB Output is correct
9 Correct 0 ms 19820 KB Output is correct
10 Correct 0 ms 19952 KB Output is correct
11 Correct 3 ms 20256 KB Output is correct
12 Correct 0 ms 19820 KB Output is correct
13 Correct 1 ms 19820 KB Output is correct
14 Correct 5 ms 20288 KB Output is correct
15 Correct 3 ms 20292 KB Output is correct
16 Memory limit exceeded 220 ms 262144 KB Memory limit exceeded
17 Halted 0 ms 0 KB -