Submission #153606

#	Time	Username	Problem	Language	Result	Execution time	Memory
153606		johutha	Sky Walking (IOI19_walk)	C++14	10 / 100	4094 ms	573456 KiB

walk

#include "walk.h"
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>

#define int long long

using namespace std;

struct graph
{
	int n = 0;
	vector<vector<pair<int,int>>> adjlist;
	vector<int> coord_x;

	int add_vertex(int x)
	{
		n++;
		adjlist.push_back(vector<pair<int,int>>());
		coord_x.push_back(x);
		return n - 1;
	}

	void add_edge(int from, int to, int w)
	{
		adjlist[from].push_back({to, w});
		adjlist[to].push_back({from, w});
	}

	int dijkstra(int s, int z)
	{
		vector<int> dists(n, -1);
		dists[s] = 0;

		priority_queue<pair<int,int>> pq;
		pq.push({0, s});

		while (!pq.empty())
		{
			int curr = pq.top().second;
			pq.pop();

			for (auto p : adjlist[curr])
			{
				int next = p.first;
				int t = p.second + dists[curr];

				if (dists[next] != -1 && t >= dists[next]) continue;

				dists[next] = t;
				pq.push({-t, next});
			}
		}
		return dists[z];
	}
};

struct graph_creator
{
	int n;

	set<int> active;
	map<int,int> last_vertices;

	vector<signed> heights;
	vector<signed> hpos;

	vector<set<int>> walk_start;
	vector<set<int>> walk_end;

	int sx, zx;
	int sv, zv;

	graph g;

	int _addv(int x, int y)
	{
		int nv = g.add_vertex(x);
		if (active.find(y) != active.end())
		{
			g.add_edge(nv, last_vertices[y], hpos[x] - hpos[g.coord_x[last_vertices[y]]]);
		}
		active.insert(y);
		last_vertices[y] = nv;
		return nv;
	}

	int create_vert(int x, int y)
	{
		int nv = _addv(x, y);
		set<int>::iterator cur = active.find(y);
		auto nx = cur;
		nx++;
		if (nx != active.end() && (*nx) <= heights[x])
		{
			int nh = (*nx);
			int hnv = _addv(x, nh);
			g.add_edge(hnv, nv, nh - y);
		}
		if (cur != active.begin())
		{
			auto prev = cur;
			prev--;
			int lh = (*prev);
			int lnv = _addv(x, lh);
			g.add_edge(nv, lnv, y - lh);
		}
		return nv;
	}

	void create()
	{
		for (int i = 0; i < n; i++)
		{
			for (auto h : walk_start[i])
			{
				create_vert(i, h);
			}
			if (i == sx)
			{
				sv = create_vert(i, 0);
			}
			else if (i == zx)
			{
				zv = create_vert(i, 0);
			}
			for (auto h : active)
			{
				if (h > heights[i]) break;
				create_vert(i, h);
			}
			for (auto h : walk_end[i])
			{
				active.erase(h);
			}
			active.erase(0);
		}
	}
};

int min_distance(vector<signed> x, vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g)
{
	graph_creator gc;
	gc.heights = h;
	gc.n = x.size();
	gc.hpos = x;
	gc.walk_start.resize(gc.n);
	gc.walk_end.resize(gc.n);
	gc.sx = s;
	gc.zx = g;
	
	int k = l.size();

	for (int i = 0; i < k; i++)
	{
		gc.walk_start[l[i]].insert(y[i]);
	}

	for (int i = 0; i < k; i++)
	{
		if (gc.walk_start[r[i]].find(y[i]) == gc.walk_start[r[i]].end())
		{
			gc.walk_end[r[i]].insert(y[i]);
		}
		else
		{
			gc.walk_start[r[i]].erase(y[i]);
		}
	}

	gc.create();

	return gc.g.dijkstra(gc.sv, gc.zv);
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43