Submission #1048887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048887		fuad27	Sky Walking (IOI19_walk)	C++17	Compilation error	0 ms	0 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
long long min_distance(std::vector<int> x, std::vector<int> h,
std::vector<int> l, std::vector<int> r, std::vector<int> y, int st, int ed) {
#define int long long
	int n = h.size();
	int m = y.size();
	vector<int> bl;
	vector<int> br(m);
	bl.resize(n);
	iota(bl.begin(),bl.end(), 0);
	iota(br.begin(),br.end(), 0);
	sort(bl.begin(), bl.end(), [&](int u, int v) -> bool {
		return h[u] > h[v];
	});
	sort(br.begin(), br.end(), [&](int u, int v) -> bool {
		return y[u] > y[v];
	});
	int p1 = 0;
	set<int> s;
	map<int,vector<int>> mp;
	map<int,vector<int>> coords;



	vector<vector<pair<int,long long>>> g;
	
	map<pair<int,int>, int> cmp;
	auto add = [&](int x, int y) -> int {
		if(cmp.find(pair<int,int>(x, y))!=cmp.end())return cmp[{x, y}];
		cmp[{x,y}]=g.size();
		coords[x].push_back(y);
		g.push_back({});
		return cmp[{x,y}];
	};
	for(int i = 0;i<m;i++) {
		while(p1 < n and h[bl[p1]] >= y[br[i]]) {
			mp[x[bl[p1]]].push_back(bl[p1]);
			s.insert(x[bl[p1++]]);	
		}
		int prev=-1;
		for(auto it = s.lower_bound(x[l[br[i]]]);it!=s.end();it++) {
			if((*it) > x[r[br[i]]])break;
			int at = (*it);
//			cout << y[br[i]] << " " << at << endl;
			if(coords[at].size())
			coords[at].push_back(y[br[i]]);
			else coords[at].push_back(0);
			add(at, y[br[i]]);
			add(at, 0);
			if(prev!=-1) {
				g[add(prev, y[br[i]])].push_back({add(at, y[br[i]]), abs(at-prev)});
				g[add(at, y[br[i]])].push_back({add(prev, y[br[i]]), abs(at-prev)});
			}
			prev=at;
		}
	}
	for(auto &i:coords) {
		sort(i.second.begin(), i.second.end());
		for(int j = 1;j<(int)(i.second).size();j++) {
//			cout << i.first << " " << i.second[j-1] << " " << i.second[j] << endl;
//			cout << i.first << " " <<  i.second[j-1] << " " << i.second[j] << endl;
			g[add(i.first, i.second[j-1])].push_back({add(i.first, i.second[j]), abs(i.second[j]-i.second[j-1])});
			g[add(i.first, i.second[j])].push_back({add(i.first, i.second[j-1]), abs(i.second[j]-i.second[j-1])});
		}
	}
//	cout << endl;
	priority_queue<pair<long long,int>> pq;
	pq.push(pair<long long, int>(0ll, add(x[st], 0)));
	vector<long long> dist(g.size(), (long long)2e18);
	dist[add(x[st], 0)] = 0;

	map<int, pair<int,int>> revs;
	for(auto i:cmp) {
		revs[i.second] = i.first;
	}
	vector<bool> vis(g.size());
	while(pq.size()) {
		int at = pq.top().second;
		if(vis[at])return;
		vis[at]=1;
//		cout << revs[at].first << " " << revs[at].second << " " << dist[at] << endl;
		pq.pop();
		for(auto [to, w]:g[at]){ 
			if(dist[to] > dist[at] + w) {
				dist[to] = dist[at]+w;
				pq.push(pair<long long, int> (-dist[to], to));
			}
		}
	}
	return dist[add(x[ed], 0)];
#undef int
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:86:14: error: return-statement with no value, in function returning 'long long int' [-fpermissive]
   86 |   if(vis[at])return;
      |              ^~~~~~