Submission #772986

#	Time	Username	Problem	Language	Result	Execution time	Memory
772986		penguin133	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	2 ms	2972 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, m;
const int sz = 100;
int dist[30005];
int brr[30005][105];
vector <int> stuf[30005];
int S[30005], P[30005], proc[30005];
 
void solve(){
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int a, b; cin >> a >> b;
		stuf[a].push_back(b);
		S[i] = a, P[i] = b;
	}
	for(int i=0;i<n;i++)for(int j=0;j<=sz;j++)brr[i][j] = 1e18;
	for(int i=0;i<n;i++)dist[i] = 1e18;
	queue <pi> q;
	q.push({S[1], -1});
	dist[S[1]] = 0;
	while(!q.empty()){
		int x = q.front().fi, y = q.front().se; q.pop();
		if(y != -1){
			if(x + y < n && brr[x + y][y] > brr[x][y] + 1)brr[x + y][y] = brr[x][y] + 1, dist[x + y] = min(dist[x + y], brr[x][y] + 1), q.push({x + y, y});
			if(x - y >= 0 && brr[x-y][y] > brr[x][y] + 1)brr[x-y][y] = brr[x][y] + 1, dist[x-y] = min(dist[x-y], brr[x][y] + 1), q.push({x-y, y});
		}
		if(!proc[x]){
			proc[x] = 1;
			for(auto i : stuf[x]){
				if(i > sz){
					for(int j = x + i; j < n; j += i){
						if(dist[j] > dist[x] + (j - x) / i)dist[j] = dist[x] + (j - x) / i, q.push({j, -1});
					}
					for(int j = x - i; j >= 0; j -= i){
						if(dist[j] > dist[x] + (x - j) / i)dist[j] = dist[x] + (x - j) / i, q.push({j, -1});
					}
				}
				else{
					y = i;
					if(x + y < n && brr[x + y][y] > dist[x] + 1)brr[x + y][y] = dist[x] + 1, dist[x + y] = min(dist[x + y], dist[x] + 1), q.push({x + y, y});
					if(x - y >= 0 && brr[x-y][y] > dist[x] + 1)brr[x-y][y] = dist[x] + 1, dist[x-y] = min(dist[x-y], dist[x] + 1), q.push({x-y, y});
				}
			}
		}
	}
	cout << (dist[S[2]] == 1e18 ? -1 : dist[S[2]]);
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

skyscraper.cpp:61:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   61 | main(){
      | ^~~~

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