oj.uz

Submission #772984

# Submission time Handle Problem Language Result Execution time Memory
772984 2023-07-04T13:40:58 Z penguin133 Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 1040 KB 
#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] = (j - x) / 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]];
}

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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1040 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1040 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Incorrect 1 ms 980 KB Output isn't correct
5 Halted 0 ms 0 KB -