oj.uz

Submission #1084535

# Submission time Handle Problem Language Result Execution time Memory
1084535 2024-09-06T11:20:10 Z peacebringer1667 Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 205 ms 215724 KB 
#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 3e4 + 5;

int B[maxn],P[maxn];
void input(int n){
    for (int i = 0 ; i < n ; i++)
      cin >> B[i] >> P[i];
}

namespace sub1{
	const int K = 2e3 + 5;
	bool check(int n){
		return (n <= K);
	}
	
	bool mark[K][K],vis[K];
	int dp[K];
	
	vector <vector<pir>> vec(100*K);
	vector <vector<int>> doge(K);

	void bfs(int n,int N){
		vec[0].push_back({B[0],P[0]});
	    
	    for (int len = 0 ; len < 100*N ; len++)
	      for (pir t : vec[len]){
	      	int Bi = t.fi,Pi = t.se;
			if (mark[Bi][Pi]) continue;
			
	      	mark[Bi][Pi] = 1;
	      	if (!vis[Bi])
			   dp[Bi] = len;
	      	
	      	if (Bi + Pi < N)
	      		vec[len + 1].push_back({Bi + Pi,Pi});
	      	if (Bi - Pi >= 0)
	      	    vec[len + 1].push_back({Bi - Pi,Pi});
	      	
	      	if (!vis[Bi])
	      	  for (int p : doge[Bi]){
	      	  	  if (Bi + p < N)
	      	  	    vec[len + 1].push_back({Bi + p,p});
	      	  	  if (Bi - p >= 0)
	      	  	    vec[len + 1].push_back({Bi - p,p});
				}
			
			vis[Bi] = 1;
		  }
	}
	
	int solve(int n,int N){
		//dp[i][k] : position i, jump k
		for (int i = 0 ; i < n ; i++)
		  doge[B[i]].push_back(P[i]);
		
		bfs(n,N);
		
		if (!vis[B[1]]) return -1;
		return dp[B[1]];
	}
}

namespace sub2{
	const int block = 150;
	
	bool vis[maxn];
	bool mark[maxn][block];
	int dp[maxn];
	
	vector <vector<pir>> vec(maxn*block + 10);
	vector <vector<int>> doge(maxn);
	
	void bfs(int n,int N){
		vec[0].push_back({B[0],P[0]});
		
		for (int len = 0 ; len < N * block ; len++)
		  for (pir t : vec[len]){
		  	int Bi = t.fi,Pi = t.se;
		  	
		  	if (Pi <= block && mark[Bi][Pi]) continue;
		  	if (Pi <= block) mark[Bi][Pi] = 1;
		  	
			if (!vis[Bi]) dp[Bi] = len;
		  	
		  	if (!vis[Bi])
		  	for (int p : doge[Bi])
		  	  if (p > block){
		  	     for (int x = Bi + p ; x < N ; x += p)
		  	       if (x < N && !vis[x])
		  	       	vec[len + (x - Bi)/p].push_back({x,p});
			     
			     for (int x = Bi - p ; x >= 0 ; x -= p)
			       if (x >= 0 && !vis[x])
			         vec[len + (Bi - x)/p].push_back({x,p});
			  }
			if (!vis[Bi])
	      	  for (int p : doge[Bi]) 
				 if (p <= block){
	      	  	  if (Bi + p < N)
	      	  	    vec[len + 1].push_back({Bi + p,p});
	      	  	  if (Bi - p >= 0)
	      	  	    vec[len + 1].push_back({Bi - p,p});
				}
		    
		    if (Pi <= block && Bi + Pi < N)
		      vec[len + 1].push_back({Bi + Pi,Pi});
		    
		    if (Pi <= block && Bi - Pi >= 0)
		      vec[len + 1].push_back({Bi - Pi,Pi});
			
			vis[Bi] = 1;
		  }
	}
	
	int solve(int n,int N){
		for (int i = 0 ; i < n ; i++)
		  doge[B[i]].push_back(P[i]);
		
		bfs(n,N);
		
		if (!vis[B[1]]) return -1;
		return dp[B[1]];
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int N,n;
	cin >> N >> n;
	input(n);
	
	if (sub1::check(N))
	  cout << sub1::solve(n,N);else
	
	cout << sub2::solve(n,N);
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 111436 KB Output is correct
2 Correct 49 ms 111440 KB Output is correct
3 Correct 43 ms 111592 KB Output is correct
4 Correct 48 ms 111444 KB Output is correct
5 Correct 50 ms 111444 KB Output is correct
6 Correct 45 ms 111436 KB Output is correct
7 Correct 48 ms 111440 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 111436 KB Output is correct
2 Correct 55 ms 111512 KB Output is correct
3 Correct 49 ms 111388 KB Output is correct
4 Correct 47 ms 111444 KB Output is correct
5 Correct 45 ms 111440 KB Output is correct
6 Correct 47 ms 111448 KB Output is correct
7 Correct 51 ms 111440 KB Output is correct
8 Correct 47 ms 111444 KB Output is correct
9 Correct 47 ms 111572 KB Output is correct
10 Correct 48 ms 111636 KB Output is correct
11 Correct 44 ms 111904 KB Output is correct
12 Correct 43 ms 111896 KB Output is correct
13 Correct 53 ms 111696 KB Output is correct
14 Correct 55 ms 112064 KB Output is correct
15 Correct 50 ms 111952 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 111440 KB Output is correct
2 Correct 48 ms 111444 KB Output is correct
3 Correct 46 ms 111440 KB Output is correct
4 Correct 50 ms 111440 KB Output is correct
5 Correct 44 ms 111456 KB Output is correct
6 Correct 52 ms 111452 KB Output is correct
7 Correct 43 ms 111440 KB Output is correct
8 Correct 66 ms 111600 KB Output is correct
9 Correct 46 ms 111700 KB Output is correct
10 Correct 45 ms 111696 KB Output is correct
11 Correct 45 ms 111964 KB Output is correct
12 Correct 50 ms 111708 KB Output is correct
13 Correct 44 ms 111700 KB Output is correct
14 Correct 46 ms 111956 KB Output is correct
15 Correct 66 ms 111840 KB Output is correct
16 Correct 46 ms 111568 KB Output is correct
17 Correct 50 ms 113232 KB Output is correct
18 Correct 56 ms 111532 KB Output is correct
19 Correct 46 ms 111468 KB Output is correct
20 Correct 49 ms 115704 KB Output is correct
21 Correct 43 ms 111444 KB Output is correct
22 Correct 45 ms 111688 KB Output is correct
23 Correct 47 ms 114772 KB Output is correct
24 Correct 53 ms 115536 KB Output is correct
25 Correct 50 ms 115652 KB Output is correct
26 Correct 51 ms 115792 KB Output is correct
27 Correct 65 ms 115796 KB Output is correct
28 Correct 70 ms 116048 KB Output is correct
29 Correct 50 ms 116560 KB Output is correct
30 Correct 48 ms 115720 KB Output is correct
31 Correct 48 ms 116052 KB Output is correct
32 Correct 47 ms 116048 KB Output is correct
33 Correct 52 ms 117584 KB Output is correct
34 Correct 48 ms 117588 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 111444 KB Output is correct
2 Correct 47 ms 111440 KB Output is correct
3 Correct 44 ms 111432 KB Output is correct
4 Correct 47 ms 111548 KB Output is correct
5 Correct 60 ms 111444 KB Output is correct
6 Correct 45 ms 111440 KB Output is correct
7 Correct 44 ms 111404 KB Output is correct
8 Correct 44 ms 111700 KB Output is correct
9 Correct 47 ms 111700 KB Output is correct
10 Correct 47 ms 111696 KB Output is correct
11 Correct 48 ms 111704 KB Output is correct
12 Correct 46 ms 111772 KB Output is correct
13 Correct 47 ms 111700 KB Output is correct
14 Correct 46 ms 111952 KB Output is correct
15 Correct 44 ms 111964 KB Output is correct
16 Correct 44 ms 111440 KB Output is correct
17 Correct 50 ms 113240 KB Output is correct
18 Correct 50 ms 111444 KB Output is correct
19 Correct 44 ms 111704 KB Output is correct
20 Correct 49 ms 115544 KB Output is correct
21 Correct 48 ms 111448 KB Output is correct
22 Correct 49 ms 111440 KB Output is correct
23 Correct 50 ms 114772 KB Output is correct
24 Correct 49 ms 115548 KB Output is correct
25 Correct 46 ms 115540 KB Output is correct
26 Correct 56 ms 115792 KB Output is correct
27 Correct 50 ms 115796 KB Output is correct
28 Correct 54 ms 116052 KB Output is correct
29 Correct 53 ms 116560 KB Output is correct
30 Correct 51 ms 115796 KB Output is correct
31 Correct 53 ms 116124 KB Output is correct
32 Correct 51 ms 116048 KB Output is correct
33 Correct 50 ms 117584 KB Output is correct
34 Correct 52 ms 117584 KB Output is correct
35 Correct 54 ms 116464 KB Output is correct
36 Correct 52 ms 114000 KB Output is correct
37 Correct 56 ms 118536 KB Output is correct
38 Correct 58 ms 118604 KB Output is correct
39 Correct 58 ms 118604 KB Output is correct
40 Correct 63 ms 118672 KB Output is correct
41 Correct 57 ms 118792 KB Output is correct
42 Correct 52 ms 116692 KB Output is correct
43 Correct 52 ms 116684 KB Output is correct
44 Correct 51 ms 116732 KB Output is correct
45 Correct 69 ms 123792 KB Output is correct
46 Correct 63 ms 123592 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 111444 KB Output is correct
2 Correct 48 ms 111436 KB Output is correct
3 Correct 46 ms 111452 KB Output is correct
4 Correct 44 ms 111444 KB Output is correct
5 Correct 49 ms 111444 KB Output is correct
6 Correct 50 ms 111588 KB Output is correct
7 Correct 48 ms 111444 KB Output is correct
8 Correct 47 ms 111440 KB Output is correct
9 Correct 49 ms 111696 KB Output is correct
10 Correct 46 ms 111700 KB Output is correct
11 Correct 52 ms 111776 KB Output is correct
12 Correct 45 ms 111700 KB Output is correct
13 Correct 45 ms 111696 KB Output is correct
14 Correct 49 ms 111952 KB Output is correct
15 Correct 49 ms 111952 KB Output is correct
16 Correct 47 ms 111620 KB Output is correct
17 Correct 53 ms 113324 KB Output is correct
18 Correct 48 ms 111708 KB Output is correct
19 Correct 43 ms 111700 KB Output is correct
20 Correct 49 ms 115540 KB Output is correct
21 Correct 46 ms 111440 KB Output is correct
22 Correct 48 ms 111584 KB Output is correct
23 Correct 56 ms 114768 KB Output is correct
24 Correct 51 ms 115540 KB Output is correct
25 Correct 50 ms 115800 KB Output is correct
26 Correct 49 ms 115612 KB Output is correct
27 Correct 53 ms 115796 KB Output is correct
28 Correct 51 ms 116048 KB Output is correct
29 Correct 56 ms 116568 KB Output is correct
30 Correct 52 ms 115804 KB Output is correct
31 Correct 48 ms 116052 KB Output is correct
32 Correct 50 ms 116060 KB Output is correct
33 Correct 55 ms 117588 KB Output is correct
34 Correct 53 ms 117588 KB Output is correct
35 Correct 52 ms 116460 KB Output is correct
36 Correct 47 ms 114000 KB Output is correct
37 Correct 56 ms 118540 KB Output is correct
38 Correct 57 ms 118604 KB Output is correct
39 Correct 62 ms 118852 KB Output is correct
40 Correct 57 ms 118792 KB Output is correct
41 Correct 59 ms 118676 KB Output is correct
42 Correct 52 ms 116892 KB Output is correct
43 Correct 51 ms 116684 KB Output is correct
44 Correct 56 ms 116684 KB Output is correct
45 Correct 65 ms 123800 KB Output is correct
46 Correct 66 ms 123592 KB Output is correct
47 Correct 69 ms 123212 KB Output is correct
48 Correct 57 ms 112464 KB Output is correct
49 Correct 63 ms 112464 KB Output is correct
50 Correct 57 ms 112208 KB Output is correct
51 Correct 70 ms 121580 KB Output is correct
52 Correct 78 ms 121940 KB Output is correct
53 Correct 67 ms 118796 KB Output is correct
54 Correct 70 ms 116560 KB Output is correct
55 Correct 59 ms 116820 KB Output is correct
56 Correct 65 ms 118812 KB Output is correct
57 Correct 70 ms 125008 KB Output is correct
58 Correct 68 ms 118988 KB Output is correct
59 Correct 71 ms 120008 KB Output is correct
60 Correct 72 ms 120012 KB Output is correct
61 Correct 65 ms 119728 KB Output is correct
62 Correct 85 ms 126564 KB Output is correct
63 Correct 77 ms 126852 KB Output is correct
64 Correct 78 ms 128684 KB Output is correct
65 Correct 111 ms 152800 KB Output is correct
66 Correct 199 ms 215724 KB Output is correct
67 Correct 205 ms 215608 KB Output is correct