Submission #26418

#	Time	Username	Problem	Language	Result	Execution time	Memory
26418		zscoder	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	246 ms	88492 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

vector<ii> graph[30001];
set<int> doge[30001];
set<int> buildings;
//priority_queue<ii, vector<ii>, greater<ii> > pq;
int dist[30001];

inline void scanint(int &x)

{
    register int c = getchar();

    x = 0;

    long long int neg = 0;

    for(;((c<48 || c>57) && c != '-');c = getchar());

    if(c=='-') {neg=1;c=getchar();}

    for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}

    if(neg) x=-x;

}
int main()
{
	//ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m;
	scanint(n);
	scanint(m);
	int x, y;
	int start, end;
	for(int i = 0; i < m; i++)
	{
		scanint(x); scanint(y);
		if(i == 0) start = x;
		else if(i == 1) end = x;
		doge[x].insert(y);
		buildings.insert(x);
	}
	int pos; int power;
	int tmp2;
	int cnt;

	for(set<int,int>::iterator it = buildings.begin(); it != buildings.end(); it++)
	//for(pos = 0; pos < n; pos++)
	{
		pos = *it;
		for(set<int,int>::iterator it2 = doge[pos].begin(); it2 != doge[pos].end(); it2++)
		{
			power = *it2;
			tmp2 = power + pos;
			cnt = 1;
			while(tmp2 < n)
			{
				graph[pos].pb(ii(tmp2, cnt));
				if(doge[tmp2].find(power) != doge[tmp2].end())
				{
					break;
				}
				cnt++;
				tmp2 += power;
			}
			cnt = -1;
			tmp2 = pos - power;
			while(tmp2 >= 0)
			{
				graph[pos].pb(ii(tmp2, -cnt));
				if(doge[tmp2].find(power) != doge[tmp2].end())
				{
					break;
				}
				cnt--;
				tmp2 -= power;
			}
		}
	}
	//cout << start << " " << end << endl;
	for(int i = 0; i < n; i++) dist[i] = 10000000;
	int yy, yz;
	dist[start] = 0;
	queue<int> q;
	set<int> qs;
	q.push(start);
	qs.insert(start);
	int yx;
	while(!q.empty())
	{
		yy = q.front();
		q.pop(); qs.erase(yy);
		for(int i = 0; i < graph[yy].size(); i++)
		{
			yz = graph[yy][i].fi; yx = graph[yy][i].se;
			if(dist[yz] > dist[yy] + yx)
			{
				dist[yz] = dist[yy] + yx;
				if(qs.find(yz) == qs.end())	{q.push(yz); qs.insert(yz);}
			}
		}
	}
	if(dist[end] >= 10000000)
	{
		cout << -1;
	}
	else cout << dist[end];
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < graph[yy].size(); i++)
                    ^
skyscraper.cpp:113:13: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if(dist[end] >= 10000000)
             ^

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