Submission #26416

#	Time	Username	Problem	Language	Result	Execution time	Memory
26416		zscoder	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1000 ms	211004 KiB

skyscraper

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int INF = int(1e9);




const int C = 62;
const int N = 30001*C;
vector<ii> adj[N+30001];
int dist[N+30001];
void addedge(int u, int v, int w)
{
	adj[u].pb(mp(v,w));
}

int getid(int u, int v)
{
	return (u*C+v);
}
set<int> S[30001];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m; cin>>n>>m;
	int s,e;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		if(i==0) s=x;
		if(i==1) e=x;
		S[x].insert(y);
	}
	for(int i=0;i<n;i++)
	{
		for(sit it = S[i].begin(); it != S[i].end(); it++)
		{
			int y=(*it);
			if(y<C)
			{
				addedge(i+N,getid(i,y),0);
				/*
				if(i-y>=0) 
				{
					addedge(getid(i,y),getid(i-y,y),1);
					//addedge(getid(i,y),i-y+N,1);
				}
				if(i+y<n) 
				{
					addedge(getid(i,y),getid(i+y,y),1);
					//addedge(getid(i,y),i+y+N,1);
				}
				*/
			}
			else
			{
				int cnt=0;
				for(int j=i+y;j<n;j+=y)
				{
					addedge(i+N,j+N,++cnt);
				}
				cnt=0;
				for(int j=i-y;j>=0;j-=y)
				{
					addedge(i+N,j+N,++cnt);
				}
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<C;j++)
		{
			if(i-j>=0) 
			{
				addedge(getid(i,j),i-j+N,1);
				addedge(getid(i,j),getid(i-j,j),1);
			}
			if(i+j<n) 
			{
				addedge(getid(i,j),getid(i+j,j),1);
				addedge(getid(i,j),i+j+N,1);
			}
		}
	}
	e+=N;
	s+=N;
	priority_queue<ii,vector<ii>,greater<ii> > pq;
	for(int i=0;i<N+30001;i++) dist[i]=INF;
	pq.push(mp(0,s));
	dist[s]=0;
	while(!pq.empty())
	{
		int d = pq.top().fi; int u = pq.top().se; pq.pop();
		//cerr<<d<<' '<<u<<'\n';
		for(int i=0;i<adj[u].size();i++)
		{
			int v=adj[u][i].fi; int w=adj[u][i].se;
			if(d+w<dist[v])
			{
				dist[v]=d+w;
				pq.push(mp(dist[v],v));
			}
		}
	}
	if(dist[e]>=INF) dist[e]=-1;
	cout<<dist[e]<<'\n';
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<adj[u].size();i++)
                ^
skyscraper.cpp:109:6: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  s+=N;
      ^
skyscraper.cpp:108:6: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
  e+=N;
      ^

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