oj.uz

Submission #18885

# Submission time Handle Problem Language Result Execution time Memory
18885 2016-02-16T11:09:14 Z chan492811 Jakarta Skyscrapers (APIO15_skyscraper) C++
10 / 100
 0 ms 5812 KB 
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

struct data{
    int to,dist;
};
struct cmp{
    bool operator()(data d1,data d2){
        return d1.dist>d2.dist;
    }
};
int n,m;
int dist[2010];
data arr[30010];
bool visit[2010],visit2[2010][2010];
vector<data> vt[2010];
priority_queue<data,vector<data>,cmp> pq;

void dij(int a){
    int i,j,flag=1,now;
    data s;
    while(flag){
        flag=0; now=21e8;
        for(i=0;i<n;i++){
            if(!visit[i] && dist[i] && dist[i]<now) a=i,flag=1,now=dist[i];
        }
        if(!flag) break; visit[a]=1;
        for(i=0;i<vt[a].size();i++){
            s=vt[a][i];
            if(!dist[s.to] || dist[s.to]>dist[a]+s.dist) dist[s.to]=dist[a]+s.dist;
        }
    }
}
int main(){
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=0;i<m;i++) scanf("%d %d",&arr[i].to,&arr[i].dist),visit[arr[i].to]=1;
    for(i=0;i<m;i++){
        visit2[arr[i].to][arr[i].to]=1;
        for(j=0;j<n;j++){
            if(!(abs(arr[i].to-j)%arr[i].dist) && !visit2[arr[i].to][j]) vt[arr[i].to].push_back((data){j,abs(arr[i].to-j)/arr[i].dist});
        }
    }
    memset(visit,0,sizeof(visit));
    dist[0]=1;
    dij(0);
    if(!visit[arr[1].to]) printf("-1");
    else printf("%d",dist[arr[1].to]-1);
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0.0 / 12.0

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

Subtask #3
0.0 / 14.0

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

Subtask #4
0.0 / 21.0

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

Subtask #5
0.0 / 43.0

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