oj.uz

Submission #490819

# Submission time Handle Problem Language Result Execution time Memory
490819 2021-11-29T12:24:53 Z hohohaha Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 406 ms 244996 KB 
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> table;

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
   fastio();
   int tc = 1;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

///#define int short
//long long
const ld pi = 4 * atan(1.0), eps = 1e-9;

const int maxn = 30000 + 5; 

//using namespace __gnu_pbds;
//gp_hash_table<int, int> table;
//const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
//struct chash {
//    int operator()(int x) const { return x ^ RANDOM; }
//};
//gp_hash_table<key, int, chash> table;

gp_hash_table<int, int> dis[maxn]; 

int n, m; 

int p[maxn]; 
int b[maxn]; 

vector<int> S[maxn]; 

const int bl = 2000; 

int disarray[maxn][bl]; 

const int inf = INT_MAX / 2; 

int * distpt(int i, int j) { 
	if(j < bl) return &disarray[i][j]; 
	auto it = dis[i].find(j); 
	if(it == dis[i].end() ) { 
		return &(dis[i][j] = inf);
	}
	return &(it->se); 
}

void solve() {
	cin >> n >> m; 	
	fori(i, 0, m - 1) { 
		int b, p; cin >> b >> p; 
		::b[i] = b; ::p[i] = p; 
		S[b].eb(p); 
	}
	
	fori(i, 0, n - 1) fori(j, 0, bl - 1) disarray[i][j] = inf; 
	
	disarray[b[0]][0] = 0; 
	
	deque<ii> q; 
	
	q.eb(b[0], 0ll); 
	
	while(!q.empty()) { 
		int i = q.front().fi, j = q.front().se; 
		
		q.of(); 
		
		if(i == b[1]) { 
			cout << *distpt(i, j); 
			return; 
		}
		
		#define ef emplace_front
		
		if(j) { 
			auto nxt = distpt(i, 0), now = distpt(i, j); 
			
//			cout << *now << endl;
			
			if(*nxt > *now) { 
				*nxt = *now; 
				q.ef(i, 0); 
			}
			for(int ti: { i - j, i + j}) { 
				if(ti >= 0 and ti < n) {
					nxt = distpt(ti, j);
					if(*nxt > *now + 1) { 
						*nxt = *now + 1; 
						q.eb(ti, j); 
					}
				}
			}
		}
		
		else { 
			auto now = distpt(i, j); 
			for(int tj: S[i]) { 
				auto nxt = distpt(i, tj); 
				if(*nxt > *now) { 
					*nxt = *now; 
					q.ef(i, tj); 
				}
			}
		} 
	}
	cout << -1; 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 6 ms 7420 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 7 ms 7376 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 8 ms 7372 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7288 KB Output is correct
3 Correct 6 ms 7372 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 6 ms 7352 KB Output is correct
7 Correct 7 ms 7352 KB Output is correct
8 Correct 6 ms 7628 KB Output is correct
9 Correct 6 ms 7756 KB Output is correct
10 Correct 7 ms 8116 KB Output is correct
11 Correct 7 ms 8140 KB Output is correct
12 Correct 6 ms 8140 KB Output is correct
13 Correct 6 ms 8140 KB Output is correct
14 Correct 6 ms 8156 KB Output is correct
15 Correct 6 ms 8140 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 6 ms 7364 KB Output is correct
4 Correct 5 ms 7388 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 7 ms 7372 KB Output is correct
7 Correct 7 ms 7372 KB Output is correct
8 Correct 6 ms 7628 KB Output is correct
9 Correct 7 ms 7756 KB Output is correct
10 Correct 7 ms 8164 KB Output is correct
11 Correct 7 ms 8140 KB Output is correct
12 Correct 7 ms 8140 KB Output is correct
13 Correct 6 ms 8152 KB Output is correct
14 Correct 6 ms 8140 KB Output is correct
15 Correct 6 ms 8152 KB Output is correct
16 Correct 6 ms 8908 KB Output is correct
17 Correct 9 ms 13252 KB Output is correct
18 Correct 13 ms 20984 KB Output is correct
19 Correct 13 ms 22968 KB Output is correct
20 Correct 14 ms 23116 KB Output is correct
21 Correct 7 ms 10444 KB Output is correct
22 Correct 12 ms 21324 KB Output is correct
23 Correct 12 ms 19916 KB Output is correct
24 Correct 14 ms 22220 KB Output is correct
25 Correct 14 ms 23088 KB Output is correct
26 Correct 14 ms 23080 KB Output is correct
27 Correct 14 ms 22996 KB Output is correct
28 Correct 14 ms 23116 KB Output is correct
29 Correct 16 ms 22992 KB Output is correct
30 Correct 14 ms 22996 KB Output is correct
31 Correct 14 ms 22988 KB Output is correct
32 Correct 14 ms 22988 KB Output is correct
33 Correct 16 ms 23052 KB Output is correct
34 Correct 16 ms 22988 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 6 ms 7420 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 7 ms 7372 KB Output is correct
8 Correct 6 ms 7628 KB Output is correct
9 Correct 6 ms 7848 KB Output is correct
10 Correct 6 ms 8140 KB Output is correct
11 Correct 7 ms 8140 KB Output is correct
12 Correct 6 ms 8148 KB Output is correct
13 Correct 6 ms 8140 KB Output is correct
14 Correct 6 ms 8140 KB Output is correct
15 Correct 6 ms 8140 KB Output is correct
16 Correct 7 ms 8908 KB Output is correct
17 Correct 9 ms 13132 KB Output is correct
18 Correct 12 ms 21068 KB Output is correct
19 Correct 15 ms 23012 KB Output is correct
20 Correct 14 ms 23116 KB Output is correct
21 Correct 8 ms 10388 KB Output is correct
22 Correct 14 ms 21324 KB Output is correct
23 Correct 13 ms 19928 KB Output is correct
24 Correct 14 ms 22300 KB Output is correct
25 Correct 15 ms 23140 KB Output is correct
26 Correct 14 ms 22988 KB Output is correct
27 Correct 16 ms 23060 KB Output is correct
28 Correct 14 ms 23068 KB Output is correct
29 Correct 14 ms 23012 KB Output is correct
30 Correct 13 ms 22988 KB Output is correct
31 Correct 14 ms 22988 KB Output is correct
32 Correct 14 ms 22988 KB Output is correct
33 Correct 17 ms 23020 KB Output is correct
34 Correct 16 ms 22988 KB Output is correct
35 Correct 17 ms 19276 KB Output is correct
36 Correct 11 ms 15960 KB Output is correct
37 Correct 18 ms 23116 KB Output is correct
38 Correct 19 ms 23768 KB Output is correct
39 Correct 18 ms 23772 KB Output is correct
40 Correct 19 ms 23812 KB Output is correct
41 Correct 27 ms 23960 KB Output is correct
42 Correct 17 ms 23612 KB Output is correct
43 Correct 16 ms 23628 KB Output is correct
44 Correct 17 ms 23716 KB Output is correct
45 Correct 29 ms 23884 KB Output is correct
46 Correct 25 ms 23824 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7376 KB Output is correct
2 Correct 5 ms 7384 KB Output is correct
3 Correct 6 ms 7380 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 6 ms 7380 KB Output is correct
7 Correct 6 ms 7464 KB Output is correct
8 Correct 6 ms 7640 KB Output is correct
9 Correct 6 ms 7768 KB Output is correct
10 Correct 6 ms 8088 KB Output is correct
11 Correct 6 ms 8152 KB Output is correct
12 Correct 7 ms 8184 KB Output is correct
13 Correct 8 ms 8152 KB Output is correct
14 Correct 7 ms 8152 KB Output is correct
15 Correct 7 ms 8180 KB Output is correct
16 Correct 7 ms 8928 KB Output is correct
17 Correct 10 ms 13156 KB Output is correct
18 Correct 13 ms 21068 KB Output is correct
19 Correct 14 ms 23000 KB Output is correct
20 Correct 14 ms 23092 KB Output is correct
21 Correct 8 ms 10448 KB Output is correct
22 Correct 13 ms 21236 KB Output is correct
23 Correct 13 ms 19928 KB Output is correct
24 Correct 15 ms 22232 KB Output is correct
25 Correct 13 ms 23004 KB Output is correct
26 Correct 14 ms 23004 KB Output is correct
27 Correct 15 ms 23024 KB Output is correct
28 Correct 16 ms 23116 KB Output is correct
29 Correct 15 ms 22992 KB Output is correct
30 Correct 14 ms 22988 KB Output is correct
31 Correct 14 ms 22992 KB Output is correct
32 Correct 16 ms 22988 KB Output is correct
33 Correct 17 ms 23096 KB Output is correct
34 Correct 15 ms 22988 KB Output is correct
35 Correct 17 ms 19356 KB Output is correct
36 Correct 11 ms 15948 KB Output is correct
37 Correct 18 ms 23128 KB Output is correct
38 Correct 19 ms 23800 KB Output is correct
39 Correct 19 ms 23756 KB Output is correct
40 Correct 21 ms 23756 KB Output is correct
41 Correct 24 ms 23948 KB Output is correct
42 Correct 16 ms 23692 KB Output is correct
43 Correct 21 ms 23652 KB Output is correct
44 Correct 17 ms 23636 KB Output is correct
45 Correct 30 ms 23804 KB Output is correct
46 Correct 22 ms 23884 KB Output is correct
47 Correct 65 ms 104900 KB Output is correct
48 Correct 86 ms 189892 KB Output is correct
49 Correct 92 ms 206816 KB Output is correct
50 Correct 99 ms 226568 KB Output is correct
51 Correct 130 ms 244036 KB Output is correct
52 Correct 125 ms 244116 KB Output is correct
53 Correct 112 ms 243356 KB Output is correct
54 Correct 104 ms 242116 KB Output is correct
55 Correct 110 ms 242176 KB Output is correct
56 Correct 113 ms 243548 KB Output is correct
57 Correct 102 ms 242276 KB Output is correct
58 Correct 107 ms 242716 KB Output is correct
59 Correct 109 ms 242960 KB Output is correct
60 Correct 115 ms 242772 KB Output is correct
61 Correct 112 ms 242860 KB Output is correct
62 Correct 142 ms 244996 KB Output is correct
63 Correct 249 ms 243012 KB Output is correct
64 Correct 279 ms 243000 KB Output is correct
65 Correct 317 ms 242988 KB Output is correct
66 Correct 406 ms 243072 KB Output is correct
67 Correct 244 ms 243072 KB Output is correct