Submission #45668

#	Time	Username	Problem	Language	Result	Execution time	Memory
45668		Trans	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	92 ms	14248 KiB

skyscraper

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <ext/pb_ds/priority_queue.hpp>

#define MAXV 30010
#define MAXE 20000000
#define INF 999999999+208

using namespace std;

struct Pair
{
    int first,second;
    Pair(){}
    Pair(int _f,int _s):first(_f),second(_s){}
};

inline bool operator>(Pair a,Pair b)
{
    return a.first>b.first;
}

int read()
{
    int ans=0;
    char ch=getchar();
    while(ch==' '||ch=='\n') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans;
}

int n,m,K;
int dist[MAXV],poslist[MAXV],tot_diff=0;
bool vis[MAXV];
int S,T;
int b[MAXV];
vector<int>p[MAXV];
vector<int>::iterator it;
bool mark[MAXV];

typedef __gnu_pbds :: priority_queue<Pair,greater<Pair>,__gnu_pbds::thin_heap_tag > Heap;
//typedef __gnu_pbds::priority_queue <Pair,greater<Pair >,__gnu_pbds::thin_heap_tag> Heap;
Heap pq;
Heap::point_iterator posmark[MAXV];

inline void update(Pair pr)
{
    if(dist[pr.second]>pr.first)
    {
        pq.modify(posmark[pr.second],pr);
        dist[pr.second]=pr.first; //!!!!!!
    }
}

int Heap_Dij()
{
    memset(dist,127,sizeof(dist));
    dist[S]=0;
    for(int i=0;i<n;i++)
        posmark[i]=pq.push(Pair(dist[i],i));
    while(!pq.empty())
    {
        Pair now=pq.top();
        pq.pop();
        if(now.first>INF) return -1;
        int i=now.second;
        if(i==T) return now.first;
        if(vis[i]) continue;
        vis[i]=true;
        for(int t=0;t<p[i].size();t++)
        {
            int P=p[i][t];
            if(t>0&&P==p[i][t-1]) continue; //!!!!!
            for(int j=i+P,k=1;j<n;j+=P,k++)
            {
                update(Pair(now.first+k,j));
                it=lower_bound(p[j].begin(),p[j].end(),P);
                if(it!=p[j].end()&&*it==P) break;
            }
            for(int j=i-P,k=1;j>=0;j-=P,k++)
            {
                update(Pair(now.first+k,j));
                it=lower_bound(p[j].begin(),p[j].end(),P);
                if(it!=p[j].end()&&*it==P) break;
            }
        }
    }
    return -1;
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int x;
        b[i]=read();
        x=read();
        p[b[i]].push_back(x);
    }
    for(int i=0;i<n;i++)
        sort(p[i].begin(),p[i].end());
    S=b[1],T=b[2];
    printf("%d\n",Heap_Dij());
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int Heap_Dij()':
skyscraper.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int t=0;t<p[i].size();t++)
                     ~^~~~~~~~~~~~

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