Submission #18885

#	Time	Username	Problem	Language	Result	Execution time	Memory
18885		chan492811	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	10 / 100	0 ms	5812 KiB

skyscraper

#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 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43