Submission #389757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
389757	2021-04-14T12:58:27 Z	milleniumEeee	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	Compilation error	0 ms	0 KB

skyscraper

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
 
const int MAXN = 30005;
const int SHIFT = 50000;
const int S = 175;
const int INF = 1e9;
 
int pos[MAXN], p[MAXN];
int n, m;
 
struct node {
	int v, pw, cost;
	node () {
		
	}
	node (int v_, int pw_, int cost_) {
		v = v_;
		pw = pw_;
		cost = cost_;
	}
};
 
struct Compare_node {
	bool operator () (node const &p1, node const &p2) {
		if (p1.cost != p2.cost) {
			return p1.cost < p2.cost;			
		}
		if (p1.v != p2.v) {
			return p1.v < p2.v;
		}
		return p1.pw < p2.pw;
	}
};
 
vector <int> big[MAXN];
vector <int> small[MAXN];
vector <node> g[MAXN][S];
int dist[MAXN][S];
 
bool in(int pos) {
	return 0 <= pos && pos < n;
}
 
signed main() {
	fastInp;
	cin >> n >> m;
	set <int> all_small;
	for (int i = 0; i < m; i++) {
		cin >> pos[i] >> p[i];
		if (p[i] >= S) {
			big[pos[i]].pb(p[i]);
		} else {
			small[pos[i]].pb(p[i]);
			all_small.insert(p[i]);
		}
	}
	// node -> v pw cost
	for (int i = 0; i < n; i++) {
		//for (int val : all_small) {
			//if (in(i - val)) {
				//g[i][val].pb(node(i - val, val, 1));
			//}
			//if (in(i + val)) {
				//g[i][val].pb(node(i + val, val, 1));
			//}
		//}
		sort(all(small[i]));
		small[i].erase(unique(all(small[i])), small[i].end());
		for (int val : small[i]) {
			g[i][0].pb(node(i, val, 0));
		}
	}
	set <node, Compare_node> pq;
	vector <bool> used(MAXN, false);
	memset(dist, -1, sizeof(dist));
	pq.insert(node(pos[0], 0, 0));
	dist[pos[0]][0] = 0;
	
	auto ers = [&](int v, int pw) {
		auto it = pq.lower_bound(node(v, pw, -INF));
		if (it != pq.end() && it->v == v && it->pw == pw) {
			pq.erase(it);
		}
	};
	
	while (!pq.empty()) {
		int v = pq.begin()->v;
		int pw = pq.begin()->pw;
		int cost = pq.begin()->cost;
		pq.erase(pq.begin());
		if (cost > dist[v][pw]) {
			continue;
		}
		if (!used[v]) { // впервые добрались до v
			used[v] = 1;
			for (int el : big[v]) {
				for (int to = v % el; to < n; to += el) {
					int c = abs(v - to) / el;
					if (dist[to][0] == -1 || dist[to][0] > cost + c) {
						dist[to][0] = cost + c;
						ers(to, 0);
						pq.insert(node(to, 0, dist[to][0]));
					}
				}
			}
		}
		// change our pw
		if (dist[v][0] == -1 || dist[v][0] > dist[v][pw]) {
			dist[v][0] = dist[v][pw];
			ers(v, 0);
			pq.insert(node(v, 0, dist[v][pw]));
		}
		for (int type = -1; type <= 1; type++) {
			if (type == 0) {
				continue;
			}
			for (int x : all_small) {
				int new_v = v + type * x;
				if (!in(new_v)) {
					continue;
				}
				int new_pw = x;			
				int c = 1;
				if (dist[new_v][new_pw] == -1 || dist[new_v][new_pw] > dist[v][pw] + c) {
					dist[new_v][new_pw] = dist[v][pw] + c;
					ers(new_v, new_pw);
					pq.insert(node(new_v, new_pw, dist[new_v][new_pw]));
				}	
			}			
		}
	}
	cout << dist[pos[1]][0] << endl;
}

Compilation message

In file included from /usr/include/c++/9/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = node; _Val = node; _KeyOfValue = std::_Identity<node>; _Compare = Compare_node; _Alloc = std::allocator<node>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<node>*]':
/usr/include/c++/9/bits/stl_tree.h:2095:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = node; _Val = node; _KeyOfValue = std::_Identity<node>; _Compare = Compare_node; _Alloc = std::allocator<node>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = node]'
/usr/include/c++/9/bits/stl_tree.h:2148:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = node; _Key = node; _Val = node; _KeyOfValue = std::_Identity<node>; _Compare = Compare_node; _Alloc = std::allocator<node>]'
/usr/include/c++/9/bits/stl_set.h:520:48:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = node; _Compare = Compare_node; _Alloc = std::allocator<node>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<node>; std::set<_Key, _Compare, _Alloc>::value_type = node]'
skyscraper.cpp:84:30:   required from here
/usr/include/c++/9/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
  780 |        is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~