Submission #430642

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
430642	2021-06-16T17:52:27 Z	saleh	Sky Walking (IOI19_walk)	C++17	Compilation error	0 ms	0 KB

walk

#include "walk.h"
#include <bits/stdc++.h>

#define int long long
#define ft first
#define sd second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 100 * 1000 + 23, MAXV = 1000 * 1000 + 23, MAXE = 4000 * 1000 + 23, INF = 1e15;

int n, m, cnt, dis[MAXV];
vector<int> add[MAXN], del[MAXN], pt[MAXN];
set<pii> s;
map<int, int> mp[MAXN];
vector<pii> pts, g[MAXV];

void dij(int v) {/*
	for (int i = 0; i < cnt; i++) {
		cout << "\\" << i << ": " << pts[i].ft << ' ' << pts[i].sd << endl << '\t';
		for (auto j : g[i]) cout << j.ft << ' ' << j.sd << '\t';
		cout << endl;
	}*/
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, v});
	for (int i = 0; i < cnt; i++) dis[i] = INF;
	dis[v] = 0;
	while (!pq.empty()) {
		pii x = pq.top();
		pq.pop();
		if (x.ft > dis[x.sd]) continue;
		for (auto i : g[x.sd]) if (dis[i.ft] > dis[x.sd] + i.sd) {
			dis[i.ft] = dis[x.sd] + i.sd;
			pq.push({dis[i.ft], i.ft});
		}
	}
}

long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int ss, int gg) {
	n = x.size();
	m = l.size();
	for (int i = 0; i < m; i++) add[l[i]].push_back(i), del[r[i]].push_back(i);
	for (int j = 0; j < n; j++) {
		for (auto i : add[j]) s.insert({y[i], i});
		pii prev = {-1, -1};
		for (auto i : s) {
			if (i.ft > h[j]) break;
			pts.push_back({i.sd, j});
			mp[i.sd][j] = cnt++;
			pt[i.sd].push_back(j);
			if (prev.sd != -1) g[cnt - 1].push_back({cnt - 2, i.ft - prev.ft}), g[cnt - 2].push_back({cnt - 1, i.ft - prev.ft});
			prev = i;
		}
		for (auto i : del[j]) s.erase({y[i], i});
	}
	for (int i = 0; i < m; i++) for (int j = 1; j < (int)pt[i].size(); j++)
		g[mp[i][pt[i][j - 1]]].push_back({mp[i][pt[i][j]], x[pt[i][j]] - x[pt[i][j - 1]]}), g[mp[i][pt[i][j]]].push_back({mp[i][pt[i][j - 1]], x[pt[i][j]] - x[pt[i][j - 1]]});
	dij(ss);
	return dis[gg];
}/*
int32_t main() { cout << min_distance({0, 4, 5, 6, 9},
{6, 6, 6, 6, 6},
{3, 1, 0},
{4, 3, 2},
{1, 3, 6},
0, 4); }*/

Compilation message

/usr/bin/ld: /tmp/cciIr808.o: in function `main':
grader.cpp:(.text.startup+0x395): undefined reference to `min_distance(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status