oj.uz

Submission #678349

# Submission time Handle Problem Language Result Execution time Memory
678349 2023-01-05T13:54:36 Z penguin133 Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 18 ms 21376 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
 
int n, m;
int S[30005], P[30005];
int dist[30005];
vector<int> pos[30005];
int go[2005][2005];
bool vis[300005];
queue<int> q[30005];
void solve(){
	cin >> n >> m;
	for(int i=0;i<m;i++)cin >> S[i] >> P[i], pos[S[i]].push_back(i);
	for(int i=0;i<m;i++)dist[i] = 1e9;
	dist[0] = 0;
	q[0].push(0);
	bool f = 0;
	for(int i=0;i<30000;i++){
		while(!q[i].empty()){
			int j = q[i].front(); q[i].pop();
			if(dist[j] < i)continue;
			if(j == 1){
				f = 1;
				break;
			}
			for(auto x : pos[S[j]]){
				if(dist[x] > i){
					dist[x] = i;
					if(P[x] != P[j])q[i].push(x);
				}
			}
			pos[S[j]].clear();
			for(int a=S[j] + P[j];a<n;a+=P[j]){
              if(i + abs(S[j] - a) / P[j] > 30000)break;
				for(auto x : pos[a]){			
					if(dist[x] <= dist[j] + abs(S[j] - S[x]) / P[j])break;
					dist[x] = i + abs(S[j] - S[x]) / P[j];
					if(dist[x] > 30000)continue;
					if(P[x] != P[j])q[dist[x]].push(x);
					break;
				}
			}
			for(int a=S[j] - P[j]; a >= 0; a-= P[j]){
              if(i + abs(S[j] - a) / P[j] > 30000)break;
				for(auto x : pos[a]){			
					if(dist[x] <= dist[j] + abs(S[j] - S[x]) / P[j])break;
					dist[x] = i + abs(S[j] - S[x]) / P[j];
					if(dist[x] > 30000)continue;
					if(P[x] != P[j])q[dist[x]].push(x);
					break;
				}
			}
		}
		if(f)break;
	}
	cout << (dist[1] == 1e9 ? -1 : dist[1]);
}
 
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:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21160 KB Output is correct
2 Correct 16 ms 21252 KB Output is correct
3 Correct 16 ms 21200 KB Output is correct
4 Correct 17 ms 21248 KB Output is correct
5 Correct 13 ms 21224 KB Output is correct
6 Correct 14 ms 21252 KB Output is correct
7 Correct 15 ms 21248 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21204 KB Output is correct
2 Correct 17 ms 21204 KB Output is correct
3 Correct 14 ms 21204 KB Output is correct
4 Correct 17 ms 21248 KB Output is correct
5 Correct 15 ms 21168 KB Output is correct
6 Correct 16 ms 21256 KB Output is correct
7 Correct 16 ms 21244 KB Output is correct
8 Correct 15 ms 21204 KB Output is correct
9 Correct 16 ms 21236 KB Output is correct
10 Correct 14 ms 21148 KB Output is correct
11 Correct 14 ms 21268 KB Output is correct
12 Correct 15 ms 21296 KB Output is correct
13 Correct 15 ms 21204 KB Output is correct
14 Correct 18 ms 21240 KB Output is correct
15 Correct 15 ms 21308 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21204 KB Output is correct
2 Correct 17 ms 21204 KB Output is correct
3 Correct 14 ms 21204 KB Output is correct
4 Correct 13 ms 21240 KB Output is correct
5 Correct 17 ms 21216 KB Output is correct
6 Correct 13 ms 21156 KB Output is correct
7 Correct 13 ms 21248 KB Output is correct
8 Correct 12 ms 21204 KB Output is correct
9 Correct 16 ms 21168 KB Output is correct
10 Correct 14 ms 21188 KB Output is correct
11 Correct 17 ms 21332 KB Output is correct
12 Correct 14 ms 21332 KB Output is correct
13 Correct 15 ms 21328 KB Output is correct
14 Correct 17 ms 21324 KB Output is correct
15 Correct 16 ms 21292 KB Output is correct
16 Correct 17 ms 21204 KB Output is correct
17 Correct 15 ms 21204 KB Output is correct
18 Correct 13 ms 21300 KB Output is correct
19 Correct 13 ms 21204 KB Output is correct
20 Correct 14 ms 21332 KB Output is correct
21 Correct 14 ms 21204 KB Output is correct
22 Correct 13 ms 21204 KB Output is correct
23 Correct 18 ms 21248 KB Output is correct
24 Correct 18 ms 21376 KB Output is correct
25 Correct 14 ms 21332 KB Output is correct
26 Incorrect 15 ms 21276 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21168 KB Output is correct
2 Correct 14 ms 21252 KB Output is correct
3 Correct 14 ms 21240 KB Output is correct
4 Correct 17 ms 21204 KB Output is correct
5 Correct 13 ms 21204 KB Output is correct
6 Correct 13 ms 21204 KB Output is correct
7 Correct 17 ms 21252 KB Output is correct
8 Correct 16 ms 21164 KB Output is correct
9 Correct 14 ms 21204 KB Output is correct
10 Correct 13 ms 21264 KB Output is correct
11 Correct 15 ms 21204 KB Output is correct
12 Correct 15 ms 21208 KB Output is correct
13 Correct 16 ms 21204 KB Output is correct
14 Correct 17 ms 21332 KB Output is correct
15 Correct 15 ms 21264 KB Output is correct
16 Correct 14 ms 21204 KB Output is correct
17 Correct 13 ms 21328 KB Output is correct
18 Correct 13 ms 21296 KB Output is correct
19 Correct 13 ms 21204 KB Output is correct
20 Correct 14 ms 21332 KB Output is correct
21 Correct 14 ms 21196 KB Output is correct
22 Correct 13 ms 21236 KB Output is correct
23 Correct 14 ms 21204 KB Output is correct
24 Correct 15 ms 21332 KB Output is correct
25 Correct 15 ms 21284 KB Output is correct
26 Incorrect 14 ms 21332 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21204 KB Output is correct
2 Correct 14 ms 21232 KB Output is correct
3 Correct 14 ms 21296 KB Output is correct
4 Correct 15 ms 21192 KB Output is correct
5 Correct 17 ms 21228 KB Output is correct
6 Correct 17 ms 21220 KB Output is correct
7 Correct 14 ms 21204 KB Output is correct
8 Correct 16 ms 21252 KB Output is correct
9 Correct 13 ms 21204 KB Output is correct
10 Correct 16 ms 21264 KB Output is correct
11 Correct 14 ms 21340 KB Output is correct
12 Correct 15 ms 21232 KB Output is correct
13 Correct 16 ms 21204 KB Output is correct
14 Correct 14 ms 21352 KB Output is correct
15 Correct 14 ms 21252 KB Output is correct
16 Correct 13 ms 21204 KB Output is correct
17 Correct 14 ms 21228 KB Output is correct
18 Correct 13 ms 21268 KB Output is correct
19 Correct 13 ms 21204 KB Output is correct
20 Correct 13 ms 21356 KB Output is correct
21 Correct 17 ms 21204 KB Output is correct
22 Correct 16 ms 21252 KB Output is correct
23 Correct 17 ms 21220 KB Output is correct
24 Correct 16 ms 21332 KB Output is correct
25 Correct 16 ms 21332 KB Output is correct
26 Incorrect 16 ms 21332 KB Output isn't correct
27 Halted 0 ms 0 KB -