Submission #40149

#	Time	Username	Problem	Language	Result	Execution time	Memory
40149		Abelyan	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	797 ms	18120 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define sc second
#define fr first
#define pr pair<int,int>
#define _mp make_pair

const int N=2006,M=30006,INF=1000000007;
int g[N][N],d[N];
priority_queue <pr> p;
pr a[M];
bool col[N];


int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i=0;i<m;i++){
	    int b,p;
	    scanf("%d%d",&b,&p);
	    a[i]=_mp(b,p);
	}
	for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            g[i][j]=INF;
        }
	}
	for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (i%a[j].sc==a[j].fr%a[j].sc){
                g[a[j].fr][i]=min(g[a[j].fr][i],abs(a[j].fr-i)/a[j].sc);
            }
        }
	}
	for (int i=0;i<n;i++){
        d[i]=INF;
	}
	d[a[0].fr]=0;
	p.push(_mp(0,a[0].fr));
	while (!p.empty()){
        int v;
        do{
           v=p.top().sc;
           p.pop();
        }while(col[v] && !p.empty());
        if (col[v] && p.empty()) break;
        col[v]=true;
        for (int i=0;i<n;i++){
            if (g[v][i]!=INF && !col[i] && d[i]>d[v]+g[v][i]){
                d[i]=d[v]+g[v][i];
                p.push(_mp(-d[i],i));
            }
        }
	}
	if (d[a[1].fr]==INF){
        cout<<-1<<endl;
        return 0;
	}
	cout<<d[a[1].fr]<<endl;
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:19:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
skyscraper.cpp:22:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d",&b,&p);
                         ^

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