Submission #108385

#	Time	Username	Problem	Language	Result	Execution time	Memory
108385		nxteru	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	729 ms	61960 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define B 300
struct t{
	int c,x,y;
};
int n,m,b[30005],p[30005];
vector<int>g[30005];
int vis[30005],d[30005][300],q[30005][200];
int main(void){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
		scanf("%d%d",b+i,p+i);
		g[b[i]].PB(i);
	}
    for(int i=0;i<n;i++){
		vis[i]=-1;
		for(int j=0;j<B;j++)d[i][j]=-1;
	}
	for(int i=0;i<m;i++)for(int j=0;j<=n/B;j++)q[i][j]=-1;
	queue<t>bfs;
	bfs.push(t{0,b[0],0});
	while(!bfs.empty()){
		int c=bfs.front().c,x=bfs.front().x,y=bfs.front().y,z=(x-b[y]%p[y])/p[y];
		bfs.pop();
		if(x<0||n<=x)continue;
		if(vis[x]==-1){
			vis[x]=c;
			for(int i=0;i<g[x].size();i++){
				int u=g[x][i];
				bfs.push(t{c+1,x-p[u],u});
				bfs.push(t{c+1,x+p[u],u});
			}
		}
		if(p[y]<B&&d[x][p[y]]==-1){
			d[x][p[y]]=c;
			bfs.push(t{c+1,x-p[y],y});
			bfs.push(t{c+1,x+p[y],y});
		}
		if(p[y]>=B&&q[y][z]==-1){
			q[y][z]=c;
			bfs.push(t{c+1,x-p[y],y});
			bfs.push(t{c+1,x+p[y],y});
		}
	}
	printf("%d\n",vis[b[1]]);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<g[x].size();i++){
                ~^~~~~~~~~~~~
skyscraper.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:14: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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43