Submission #335234

#	Time	Username	Problem	Language	Result	Execution time	Memory
335234		hivakarami	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	407 ms	262148 KiB

skyscraper

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef long double doublel;
#define f first
#define s second
 
const int N = 3e5 + 100;
const ll base = 313;
const ll mod = 1e9 + 9;	
const int inf = 1e8;	

set<pair<int, int>> s;
int dis[N];
vector<pair<int, int>> adj[N];

int n, m, b, p;

void dij(int u)
{
	for(int i = 0; i < n; i++)
		dis[i] = inf;
	dis[u] = 0;
	for(int i = 0; i < n; i++)	
		s.insert({dis[i], i});
	while(!s.empty())
	{
		int x = s.begin() -> s;
		s.erase(s.begin());
		
		for(auto y : adj[x])
		{
			if(dis[y.f] > dis[x] + y.s)
			{
				s.erase({dis[y.f], y.f});
				dis[y.f] = dis[x] + y.s;
				s.insert({dis[y.f], y.f});
			}
		}
	}	
		
		
}





int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	

	int x, y;
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		cin >> b >> p;
		for(int i = b+p; i < n; i += p)
		{
			adj[b].push_back({i, (i-b)/p});
			//cout << i << ' ' << b << ' ' << (i-b)/p << endl; 
		}
			
		for(int i = b-p; i >= 0; i -= p)
		{
			adj[b].push_back({i, (b-i)/p});
			//cout << i << ' ' << b << ' ' << (b-i)/p << endl;
		}
		
		if(i == 0)
			x = b;
		if(i == 1)
			y = b;
		
	}
	
	dij(x);
	
	if(dis[y] >= inf)
		dis[y] = -1;
	cout << dis[y] << endl;
	
	
	

    return 0;
}

 
 	
 	


/*
5 3
0 2
1 1
4 1
*/





 

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:83:15: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |  cout << dis[y] << endl;
      |               ^
skyscraper.cpp:79:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |  dij(x);
      |  ~~~^~~

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