Submission #106996

#	Time	Username	Problem	Language	Result	Execution time	Memory
106996		nxteru	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	4 ms	1152 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000000
#define B 173
#define R 1000000000
int n,m,dn[30005][205],dm[30005][205],st[30005],ed[30005],p[30005],b[30005],rs[30005];
bool d[30005][305];
vector<int>g[30005];
int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",b+i,p+i);
		st[i]=b[i]%p[i];
		rs[i]=(b[i]-st[i])/p[i];
		ed[i]=(n-st[i]-1)/p[i]+1;
		if(p[i]<=B)d[b[i]][p[i]]=true;
		else g[b[i]].PB(i);
	}
	for(int i=0;i<n;i++)for(int j=0;j<=B;j++)dn[i][j]=INF;
	for(int i=0;i<m;i++)for(int j=0;j<ed[i];j++)dm[i][j]=INF;
	priority_queue<P,vector<P>,greater<P> >dik;
	dn[b[0]][0]=0;
	dik.push(P(0,b[0]*n));
	while(!dik.empty()){
		int c=dik.top().F,x=dik.top().S;
		dik.pop();
		if(x<R){
			int e=x%n,v=x/n;
			if(dn[v][e]<c)continue;
			if(e==0){
				for(int i=1;i<=B;i++){
					if(d[v][i]&&dn[v][i]>c){
						dn[v][i]=c;
						dik.push(P(c,v*n+i));
					}
				}
				for(int i=0;i<g[v].size();i++){
					int r=g[v][i],w=(v-st[r])/p[r];
					if(dm[r][w]>c){
						dm[r][w]=c;
						dik.push(P(dm[r][w],R+r*m+w));
					}
				}
			}else{
				if(v+e<n&&dn[v+e][e]>c+1){
					dn[v+e][e]=c+1;
					dik.push(P(c+1,n*(v+e)+e));
				}
				if(v-e>=0&&dn[v-e][e]>c+1){
					dn[v-e][e]=c+1;
					dik.push(P(c+1,n*(v-e)+e));
				}
				if(dn[v][0]>c){
					dn[v][0]=c;
					dik.push(P(c,v*n));
				}
			}
		}else{
			x-=R;
			int r=x/m,w=x%m,v=st[r]+w*p[r];
			if(dm[r][w]<c)continue;
			if(dn[v][0]>c){
				dn[v][0]=c;
				dik.push(P(c,v*n));
			}
			if(w+1<ed[r]&&dm[r][w+1]>c+1){
				dm[r][w+1]=c+1;
				dik.push(P(c+1,R+r*m+w+1));
			}
			if(w-1>=0&&dm[r][w-1]>c+1){
				dm[r][w-1]=c+1;
				dik.push(P(c+1,R+r*m+w-1));
			}
		}
	}
	if(dn[b[1]][0]==INF)dn[b[1]][0]=-1;
	printf("%d\n",dn[b[1]][0]);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:44:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++){
                 ~^~~~~~~~~~~~
skyscraper.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",b+i,p+i);
   ~~~~~^~~~~~~~~~~~~~~~

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