Submission #222908

#	Time	Username	Problem	Language	Result	Execution time	Memory
222908		johutha	Sky Walking (IOI19_walk)	C++17	100 / 100	2396 ms	138360 KiB

walk

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

#define int long long

using namespace std;

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

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

	void addedge(int a, int b, int w)
	{
		adjlist[a].push_back({b, w});
		adjlist[b].push_back({a, w});
	}
	
	void print()
	{
		for (int i = 0; i < n; i++)
		{
			cout << i << ": ";
			for (auto p : adjlist[i])
			{
				cout << "(" << p.first << ", " << p.second << ") ";
			}
			cout << "\n";
		}
	}

    int dijkstra(int s, int tg)
    {
		vector<int> dist;
        priority_queue<pair<int,int>> pq;
        dist.resize(n, -1);
        dist[s] = 0;
        pq.push({0, s});

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

            if (dist[curr] != -1 && d > dist[curr]) continue;

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

                if (dist[next] != -1 && dist[next] <= t) continue;

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

struct skywalk
{
	int l, r, y;
};

struct building
{
	int x, h;
};

vector<skywalk> splitwalks(vector<skywalk> skw, const vector<building>& buildings, int ind)
{
	int n = skw.size();
	int nb = buildings.size();
	vector<int> a(n, -1);
	vector<int> b(n, -1);

	int c = ind;

	for (int i = 0; i < n; i++)
	{
		while (skw[i].y > buildings[c].h && c > 0) c--;
		a[i] = c;
	}

	c = ind;

	for (int i = 0; i < n; i++)
	{
		while (skw[i].y > buildings[c].h && c < nb - 1) c++;
		b[i] = c;
	}

	vector<skywalk> nsk;
	for (int i = 0; i < n; i++)
	{
		if (a[i] == -1 || b[i] == -1 || a[i] >= skw[i].r || skw[i].l >= b[i]) nsk.push_back(skw[i]);
		else
		{
			if (skw[i].l != a[i]) nsk.push_back({skw[i].l, a[i], skw[i].y});
			if (a[i] != b[i]) nsk.push_back({a[i], b[i], skw[i].y});
			if (b[i] != skw[i].r) nsk.push_back({b[i], skw[i].r, skw[i].y});
		}
	}
	return nsk;
}

struct hf
{
	vector<int> ip;

	void pre()
	{
		ip.push_back(0);
		ip.push_back(1e16);
		sort(ip.begin(), ip.end());
		ip.erase(unique(ip.begin(), ip.end()), ip.end());
	}

	int operator()(int i)
	{
		return lower_bound(ip.begin(), ip.end(), i) - ip.begin();
	}
};

template<typename v>
struct fastmap
{
	hf cm;
	vector<v> vals;

	fastmap(){}
	fastmap(hf icm, v inv) : cm(icm), vals(vector<v>(icm.ip.size(), inv)) {}

	v& operator()(int y)
	{
		return vals[cm(y)];
	}
};

struct event
{
	int x;
	bool st;
	int nr;
};

struct graphcreator
{
	int n;
	hf hcomp;

	vector<building> buildings;
	vector<skywalk> walks;

	fastmap<int> lastv;
	fastmap<int> lastx;
	set<int> active;

	graph g;

	pair<int,int> construct(int is, int it)
	{
		int stv = -1, env = -1;
		n = buildings.size();
		vector<vector<int>> start(n);
		vector<vector<int>> stop(n);

		for (auto w : walks)
		{
			start[w.l].push_back(w.y);
			stop[w.r].push_back(w.y);
			hcomp.ip.push_back(w.y);
		}
		hcomp.pre();
		lastv = fastmap<int>(hcomp, -1);
		lastx = fastmap<int>(hcomp, -1);

		for (int cb = 0; cb < n; cb++)
		{
			vector<int> newvert;
			if (cb == is || cb == it) newvert.push_back(0);
			for (auto y : stop[cb])
			{
				newvert.push_back(y);
				if (active.upper_bound(y) != active.end()) newvert.push_back(*active.upper_bound(y));
				if (active.lower_bound(y) != active.begin()) newvert.push_back(*prev(active.lower_bound(y)));
			}
			for (auto y : start[cb])
			{
				newvert.push_back(y);
				if (active.upper_bound(y) != active.end()) newvert.push_back(*active.upper_bound(y));
				if (active.lower_bound(y) != active.begin()) newvert.push_back(*prev(active.lower_bound(y)));
			}
			sort(newvert.begin(), newvert.end());
			newvert.erase(unique(newvert.begin(), newvert.end()), newvert.end());
			vector<int> verts;
			int last = -1;
			for (auto i : newvert)
			{
				if (i > buildings[cb].h) continue;
				verts.push_back(g.addvertex());
				if (last != -1)
				{
					g.addedge(verts[verts.size() - 2], verts.back(), i - last);
				}
				if (active.count(i))
				{
					g.addedge(lastv(i), verts.back(), buildings[cb].x - lastx(i));
				}
				lastx(i) = buildings[cb].x;
				lastv(i) = verts.back();
				last = i;
			}
			if (cb == is) stv = verts[0];
			if (cb == it) env = verts[0];
			for (auto i : stop[cb]) active.erase(i);
			for (auto i : start[cb]) active.insert(i);
		}
		return {stv, env};
	}
};

int min_distance(vector<signed> ix, vector<signed> ih, vector<signed> il, vector<signed> ir, vector<signed> iy, signed is, signed it)
{
	vector<building> buildings;
	vector<skywalk> oldwalks;

	for (int i = 0; i < (int)ix.size(); i++) buildings.push_back({ix[i], ih[i]});

	for (int i = 0; i < (int)il.size(); i++)
	{
		oldwalks.push_back({il[i], ir[i], iy[i]});
	}

	sort(oldwalks.begin(), oldwalks.end(), [&](const skywalk &w1, const skywalk &w2)
	{
		return w1.y < w2.y;
	});

	oldwalks = splitwalks(oldwalks, buildings, is);

	sort(oldwalks.begin(), oldwalks.end(), [&](const skywalk &w1, const skywalk &w2)
	{
		return w1.y < w2.y;
	});

	vector<skywalk> walks = splitwalks(oldwalks, buildings, it);
	
	graphcreator gc;
	gc.buildings = buildings;
	gc.walks = walks;
	auto p = gc.construct(is, it);

	if (p == make_pair(-1ll, -1ll)) return -1;

	return gc.g.dijkstra(p.first, p.second);
}

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