Submission #18884

#	Time	Username	Problem	Language	Result	Execution time	Memory
18884		chan492811	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	36 / 100	1000 ms	34868 KiB

skyscraper

#include <cstdio>
#include <queue>
#include <vector>
#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[30010];
data arr[30010];
bool visit[30010];
vector<data> vt[30010];
priority_queue<data,vector<data>,cmp> pq;

void dij(int a){
    int i;
    data s;
    pq.push((data){a,1});
    while(!pq.empty()){
        a=pq.top().to; pq.pop();
        if(visit[a]) continue; visit[a]=1;
        for(i=0;i<vt[a].size();i++){
            s=vt[a][i];
            if(dist[s.to]==0 || dist[s.to]>dist[a]+s.dist){
                pq.push((data){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);
    for(i=0;i<m;i++){
        for(j=i+1;j<m;j++){
            if(!(abs(arr[i].to-arr[j].to)%arr[i].dist)) vt[i].push_back((data){j,abs(arr[i].to-arr[j].to)/arr[i].dist});
            if(!(abs(arr[i].to-arr[j].to)%arr[j].dist)) vt[j].push_back((data){i,abs(arr[i].to-arr[j].to)/arr[j].dist});
        }
    }
    dist[0]=1;
    dij(0);
    if(!visit[1]) printf("-1");
    else printf("%d",dist[1]-1);
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43