Submission #570685

#	Time	Username	Problem	Language	Result	Execution time	Memory
570685		nayhz	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	492 ms	112756 KiB

skyscraper

// hkoi AP152 Jakarta Skyscrapers
#include <bits/stdc++.h>
#define lck cout << "ick bmi 32.9\n"
#define cam_cs cout << "ick orz\n"
#define orz(x) cout << (x) << " orz\n"

#define pii pair<int, int>
#define pll pair<long long, long long>
#define pcc pair<char, char>
#define ll long long
#define ull unsigned long long
#define ld long double
#define int long long

#define vi vector<int>
#define vll vector<long long>
#define vd vector<double>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<long long, long long>>

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define SET(x, a) memset((x), a, sizeof (x))

#define yes() cout << "YES\n"
#define no() cout << "NO\n"
#define impossible() cout << "Impossible\n"

#define inf 0x3f

template<typename T, typename V>
inline void print (const std::pair<T, V> &x) {std::cout << x.first << ' ' << x.second << '\n';}
template<typename T>
inline void print (const T &x) {std::cout << x << '\n';}
template<typename T>
inline void print (std::vector<T> &x) {for (auto &y : x) std::cout << y << " "; std::cout << '\n';}
inline void print () {std::cout << '\n';}
using namespace std;

ld pi = acos(-1);
ld eps = 1e-9;
ll mod = 1000000007;

inline ll powmod(ll a, ll b) {ll res = 1; a %= mod; for(; b; b >>= 1) {if (b & 1) res = res * a % mod; a = a * a % mod;} return res;}
inline ll hamming (string &a, string &b) {ll ret = 0; for (ll i = 0; i < a.length(); i++) if (a[i] != b[i]) ret++; return ret;}
inline bool isprime (ll x) {if (x == 2) return true; for (ll i = 2; i * i <= x; i++) {if (x % i == 0) return false;}; return true;}
inline double Dist (double x1, double y1, double x2, double y2) {return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));}
inline ll manhattan (ll x1, ll y1, ll x2, ll y2) {return abs(x1 - x2) + abs(y1 - y2);}
clock_t T, NT;
inline double get_time() {NT = clock() - T; return (double)(NT) / CLOCKS_PER_SEC;}

struct dsu {
	int n;
	vector<int> parent;
	vector<int> sz;
	dsu (int _n) : n(_n) {
		parent.resize(n + 5);
		iota(all(parent), 0);
		sz.assign(n, 1);
	}
	inline void init (int _n) {n = _n; parent.resize(n); iota(all(parent), 0); sz.assign(n, 1);}
	inline void init () {iota(all(parent), 0); sz.assign(n, 1);}
	inline int Find (int x) {return parent[x] == x ? x : parent[x] = Find(parent[x]);}
	inline bool Union (int x, int y) {
		x = Find(x), y = Find(y);
		if (x != y) {
			parent[x] = y;
			sz[y] += sz[x], sz[x] = 0;
			return true;
		}
		else return false;
	}
};
struct segment_tree {
	ll n;
	vll a; // 1-based
	vll seg; // 1-based

	segment_tree (int _n) : n(_n) {
		a.resize(n + 5);
		seg.resize(4 * n + 5);
	}
	inline void build (int l, int r, int id = 1) {
		if (l == r) {seg[id] = a[l]; return;}
		ll mid = (l + r) >> 1;
		build(l, mid, id << 1);
		build(mid + 1, r, id << 1 | 1);

		seg[id] = max(seg[id << 1], seg[id << 1 | 1]); // SUBJECT TO CHANGE ACCORDING TO TASK
	}
	inline ll query (int lq, int rq, int l, int r, int id = 1) {
		if (r < lq || rq < l) return -1;
		else if (lq <= l && r <= rq) return seg[id];
		ll mid = (l + r) >> 1;
		ll v1 = query(lq, rq, l, mid, id << 1);
		ll v2 = query(lq, rq, mid + 1, r, id << 1 | 1);
		if (v1 == -1) return v2;
		else if (v2 == -1) return v1;
		else return max(v1, v2); // SUBJECT TO CHANGE ACCORDING TO TASK
	}
};
struct TopoSort {
	int n;
	vi in, ans;
	vector<vi> adj;
	inline void init (int _n) {n = _n; in.assign(n, 0); adj.assign(n, vector<int> (0));}
	inline void conn (int x, int y) {adj[x].push_back(y), ++in[y];}
	inline bool sort () {
		queue<int> q; 
		for (int i = 0; i < n; i++) if (!in[i]) q.push(i);
		while (!q.empty()) {
			int curr = q.front();
			q.pop();
			ans.push_back(curr);
			for (auto &x : adj[curr]) if (!(--in[x])) q.push(x);
		}
		return ans.size() == n;
	}
};
struct Fenwick {
	ll n;
	vll a;
	Fenwick (ll _n): n(_n), a(_n) {}
	void add (ll x, ll val) {
		for (int i = x + 1; i <= n; i += i & -i) a[i - 1] += val;
	}
	ll sum (ll x) {
		ll ans = 0;
		for (int i = x; i >= 1; i -= i & -i) ans += a[i - 1];
		return ans;
	}
	ll range_sum (ll l, ll r) {return sum(r) - sum(l);}
};

/*
>>>>>>>>>>>>>>>>>>>>>>>>>>END OF TEMPLATE HEADER<<<<<<<<<<<<<<<<<<<<<<<<
*/

pii a[30005];
vi adj[30005];
bitset<30005> visited[30005];

void solve (int &tc) {
	int n, m; cin >> n >> m;
	int s, e;
	SET(visited, false);

	for (int i = 0; i < m; i++) {
		cin >> a[i].fi >> a[i].se;
		if (!i) s = a[i].fi;
		if (i == 1) e = a[i].fi;

		if (0 <= a[i].fi + a[i].se && a[i].fi + a[i].se < n) adj[a[i].fi].push_back(a[i].se);
		if (0 <= a[i].fi - a[i].se && a[i].fi - a[i].se < n) adj[a[i].fi].push_back(-a[i].se);
	}

	queue<pair<int, pii>> q;
	q.push({s, {0, 0}});
	pair<int, pii> curr;
	while (!q.empty()) {
		curr = q.front();
		q.pop();

		if (curr.fi == e) {
			print((curr.se.fi));
			return;
		}

		if (0 <= curr.fi + curr.se.se && curr.fi + curr.se.se < n && !visited[curr.fi][curr.fi + curr.se.se]) {
			q.push({curr.fi + curr.se.se, {curr.se.fi + 1, curr.se.se}});
			visited[curr.fi].set(curr.fi + curr.se.se);
		}
		
		for (auto &x : adj[curr.fi]) {
			if (x && !visited[curr.fi][curr.fi + x]) q.push({curr.fi + x, {curr.se.fi + 1, x}}), visited[curr.fi].set(curr.fi + x);
		}
	}
	print((-1));
}

signed main () {
	cin.tie()->sync_with_stdio(false);
	T = clock();
	srand(time(NULL));
	
	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
		// if (i != t) cout << '\n';
	}
	// while (true) {solve(t); t++;}
	return 0;
}

// g++ -std=c++17 file_name.cpp -o file_name

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message (stderr)

skyscraper.cpp: In function 'long long int hamming(std::string&, std::string&)':
skyscraper.cpp:47:72: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 | inline ll hamming (string &a, string &b) {ll ret = 0; for (ll i = 0; i < a.length(); i++) if (a[i] != b[i]) ret++; return ret;}
      |                                                                      ~~^~~~~~~~~~~~
skyscraper.cpp: In member function 'bool TopoSort::sort()':
skyscraper.cpp:119:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  119 |   return ans.size() == n;
      |          ~~~~~~~~~~~^~~~
skyscraper.cpp: In function 'void solve(long long int&)':
skyscraper.cpp:25:44: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'class std::bitset<30005>'; use assignment or value-initialization instead [-Wclass-memaccess]
   25 | #define SET(x, a) memset((x), a, sizeof (x))
      |                                            ^
skyscraper.cpp:148:2: note: in expansion of macro 'SET'
  148 |  SET(visited, false);
      |  ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:66,
                 from skyscraper.cpp:2:
/usr/include/c++/10/bitset:751:11: note: 'class std::bitset<30005>' declared here
  751 |     class bitset
      |           ^~~~~~
skyscraper.cpp:166:3: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
  166 |   if (curr.fi == e) {
      |   ^~

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