Submission #483496

#	Time	Username	Problem	Language	Result	Execution time	Memory
483496		blue	Sky Walking (IOI19_walk)	C++17	10 / 100	4112 ms	281124 KiB

walk

#include "walk.h"
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;

int N;
vector<int> X;
vector<int> H;

int M;
vector<int> L;
vector<int> R;
vector<int> Y;

int S;
int G;


int ht(int i)
{
	if(i > 0) return H[i-1];
	else return Y[-i-1];
}

bool cmp(int i, int j)
{
	if(ht(i) == ht(j)) return i > j;
	else return ht(i) > ht(j);
}


vector<int> newL, newR, newY;




const int mx = 4'000'000;
const long long INF = 1'000'000'000'000'000'000LL;


vector<int> edge[mx];
vector<long long> wt[mx];

void add_edge(int u, int v, long long w)
{
	cerr << "add edge " << u << ' ' << v << ' ' << w << '\n';
	edge[u].push_back(v);
	wt[u].push_back(w);

	edge[v].push_back(u);
	wt[v].push_back(w);
}

vector<long long> distS(mx, INF);

struct distcomp
{
	int i;
};

bool operator < (distcomp A, distcomp B)
{
	if(distS[A.i] == distS[B.i]) return A.i < B.i;
	return distS[A.i] < distS[B.i];
}


set<pair<int, int> > points;  //stored by building index + y coordinate







struct loc
{
	int b;
	int y;

	int ind;
};

bool operator < (loc A, loc B)
{
	if(A.y == B.y) return A.b < B.b;
	else return A.y < B.y;
}



long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
	N = int(x.size());
	X = x;
	H = h;

	M = int(l.size());
	L = l;
	R = r;
	Y = y;

	S = s;
	G = g;



	vector<int> obj;
	for(int i = 0; i < N; i++) obj.push_back(i+1);
	for(int j = 0; j < M; j++) obj.push_back(-(j+1));
	sort(obj.begin(), obj.end(), cmp);

	vector<int> walk_buildings[M];

	set<int> buildings;
	for(int o: obj)
	{
		if(o > 0)
		{
			buildings.insert(o-1);
		}
		else
		{
			int w = -o-1;
			set<int> endpoints;
			endpoints.insert(L[w]);
			endpoints.insert(R[w]);
			points.insert(make_pair(L[w], Y[w]));
			cerr << "inserting point A " << L[w] << ' ' << Y[w] << '\n';
			points.insert(make_pair(R[w], Y[w]));
			cerr << "inserting point B " << R[w] << ' ' << Y[w] << '\n';
			walk_buildings[w].push_back(L[w]);
			walk_buildings[w].push_back(R[w]);

			for(int z: {s, g})
			{
				auto f = buildings.lower_bound(z);
				if(f != buildings.end())
					if(L[w] < *f && *f < R[w])
					{
						points.insert(make_pair(*f, Y[w]));
						cerr << "inserting point C " << *f << ' ' << Y[w] << '\n';
						walk_buildings[w].push_back(*f);
					}
						// endpoints.insert(*f);

				if(f != buildings.begin())
				{
					f--;
					if(L[w] < *f && *f < R[w])
					{
						points.insert(make_pair(*f, Y[w]));
						cerr << "inserting point D " << *f << ' ' << Y[w] << '\n';
						walk_buildings[w].push_back(*f);
					}
				}
			}
		}
	}

	vector<int> ep[N];

	for(int j = 0; j < M; j++)
	{
		walk_buildings[j].erase(unique(walk_buildings[j].begin(), walk_buildings[j].end()), walk_buildings[j].end());
		for(int i: walk_buildings[j])
			ep[i].push_back(j);
	}

	points.insert(make_pair(S, 0));
	points.insert(make_pair(G, 0));


	vector<int> left_ep[N], right_ep[N];
	for(int j = 0; j < M; j++)
	{
		left_ep[L[j]].push_back(j);
		right_ep[R[j]].push_back(j);
	}

	set< pair<int, int> > curr_walks;
	for(int i = 0; i < N; i++)
	{
		for(int w: left_ep[i])
		{
			curr_walks.insert(make_pair(Y[w], w));
		}

		for(int w: ep[i])
		{
			auto f = curr_walks.find(make_pair(Y[w], w));
			assert(f != curr_walks.end());
			auto f1 = f;

			if(f != curr_walks.begin())
			{
				f--;
				if(L[f->second] <= i && i <= R[f->second] && Y[f->second] <= H[i])
					points.insert(make_pair(i, f->first));
				// cerr << "inserting point " << *f << ' ' << Y[w] << '\n';
			}

			if(f1 != curr_walks.end())
			{
				f1++;
				if(f1 != curr_walks.end())
					if(L[f1->second] <= i && i <= R[f1->second] && Y[f1->second] <= H[i])
						points.insert(make_pair(i, f1->first));
			}
		}

		for(int w: right_ep[i])
		{
			curr_walks.erase(make_pair(Y[w], w));
		}
	}

		cerr << "all points: ";
		for(auto p:points) cerr << p.first << ' ' << p.second << '\n';

	vector<loc> places;

	int ct = -1;
	for(auto p: points)
	{
		ct++;
		places.push_back(loc{p.first, p.second, ct});
	}

	sort(places.begin(), places.end(), [] (loc k, loc l)
	{
		if(k.b == l.b)
			return k.y < l.y;
		else
			return k.b < l.b;
	});

	cerr << "vertical edges: \n";

	for(int i = 0; i+1 < int(places.size()); i++)
	{
		if(places[i].b == places[i+1].b)
			add_edge(places[i].ind, places[i+1].ind, places[i+1].y - places[i].y);
	}

	sort(places.begin(), places.end(), [] (loc k, loc l)
	{
		if(k.y == l.y)
			return k.b < l.b;
		else
			return k.y < l.y;
	});

	cerr << "horiz edges: \n";

	cerr << "\n\n\n\nsorted places: \n";
	for(auto q: places) cerr << q.b << ' ' << q.y << ' ' << q.ind << '\n';
	cerr << "\n\n\n";

	for(int j = 0; j < M; j++)
	{
		cerr << "j = " << j << '\n';
		auto f = lower_bound(places.begin(), places.end(), loc{L[j], Y[j], -1});
		auto g = f;
		g++;

		int ite = 0;

		while(1)
		{
			cerr << "ite = " << ite << '\n';
			ite++;
			cerr << int(g == places.end()) << '\n';
			if(g == places.end()) break;
			if(g->b > R[j]) break;
			if(g->y != Y[j]) break;
			// cerr << "gb = " << g->b << ", fb = " << f->b << '\n';
			cerr << "g = " << g->b << ' ' << g->y << ", " << "f = " << f->b << ' ' << f->y << '\n';
			add_edge(f->ind, g->ind, X[g->b] - X[f->b]);
			f++;
			g++;
			cerr << "done\n";
		}
	}
	cerr << "j done\n";

	int S_loc, G_loc;

	for(int i = 0; i <= ct; i++)
	{
		if(places[i].b == S && places[i].y == 0)
			S_loc = places[i].ind;
		else if(places[i].b == G && places[i].y == 0)
			G_loc = places[i].ind;
	}


	for(int i = 0; i <= ct; i++) cerr << "position " << places[i].b << ' ' << places[i].y << " = index " << places[i].ind << '\n';


	distS[S_loc] = 0;

	set<distcomp> tbv;
	for(int i = 0; i <= ct; i++)
		tbv.insert(distcomp{i});

	cerr << "hello\n";


	while(!tbv.empty())
	{
		int u = tbv.begin()->i;
		tbv.erase(tbv.begin());

		cerr << "u = " << u << ", distS = " << distS[u] << '\n';

		for(int e = 0; e < int(edge[u].size()); e++)
		{
			int v = edge[u][e];
			long long w = wt[u][e];

			if(distS[v] <= distS[u] + w) continue;
			tbv.erase(distcomp{v});
			distS[v] = distS[u] + w;
			tbv.insert(distcomp{v});
		}
	}

	if(distS[G_loc] >= INF)
		distS[G_loc] = -1;

	return distS[G_loc];
}

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:304:13: warning: 'S_loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  304 |  distS[S_loc] = 0;
      |             ^
walk.cpp:332:16: warning: 'G_loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  332 |  if(distS[G_loc] >= INF)
      |                ^

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