Submission #417253

#	Time	Username	Problem	Language	Result	Execution time	Memory
417253		Kevin_Zhang_TW	Sky Walking (IOI19_walk)	C++17	100 / 100	2268 ms	274384 KiB

walk

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
 
 
// TODO Watch out for the size
const int MAX_N = 400010 * 10;
const ll inf = 1ll << 55;
#include "walk.h"
 
// graph is 0 based
int n, m;
vector<int> xup[MAX_N];
vector<int> x, h, pfsz;
vector<pair<int,int>> edge[MAX_N];
 
int get_id(int i, int j) {
	assert(binary_search(AI(xup[i]), j));
	return lower_bound(AI(xup[i]), j) - begin(xup[i]) + pfsz[i];
}
 
 
const int C = MAX_N;
 
void sweep(vector<int> l, vector<int> r, vector<int> y) {
	set<int> ally;
	vector<vector<int>> in(n + 10), out(n + 10);
	for (int i = 0;i < m;++i) {
		if (r[i] - l[i] + 1 <= 2) continue;
		DE(l[i], r[i], y[i]);
		in[l[i]+1].pb(y[i]);
		out[r[i]].pb(y[i]);
	}
 
	for (int i = 0;i < n;++i) {
		for (int j : out[i]) ally.erase(j);
		for (int j : in[i]) ally.insert(j);
 
		vector<int> ep = xup[i];
 
		if (false && ep.size() && ep[0] == 0) {
			xup[i].insert(end(xup[i]), AI(ally));
			continue;
		}
 
//		auto it = begin(ally), rit = ally.upper_bound(h[i]);
//		for (int j = 0;j < C && it != rit;++j) {
//			xup[i].pb(*it++);
//		}
//		for (int j = 0;j < C && it != rit;++j)
//			xup[i].pb(*--rit);
 
		ep.pb(0), ep.pb(h[i]);
		for (int j : ep) {
			auto it = ally.upper_bound(j);
			{
				auto c = it;
				if (c != end(ally)) xup[i].pb(*c++);
				//if (c != end(ally)) xup[i].pb(*c++);
			}
			//if (it != begin(ally)) xup[i].pb(*prev(it)), --it;
			if (it != begin(ally)) xup[i].pb(*prev(it));
		}
	}
}
void init_ver(std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
//	for (int i = 0;i < m;++i) {
//		for (int j = l[i];j <= r[i];++j) {
//			if (h[j] < y[i]) continue;
//			xup[j].pb(y[i]);
//		}
//	}
//	for (int i = 0;i < n;++i) {
//		sort(AI(xup[i]));
//		xup[i].erase(unique(AI(xup[i])), end(xup[i]));
//		if (xup[i].size() < C * 2) continue;
//		vector<int> e(end(xup[i])-C, end(xup[i]));
//		xup[i].resize(C);
//		xup[i].insert(end(xup[i]), AI(e));
//	}
//
 
	xup[s].pb(0), xup[g].pb(0);
 
	for (int i = 0;i < m;++i) {
		xup[ l[i] ].pb( y[i] );
		xup[ r[i] ].pb( y[i] );
	}
 
	sweep(l, r, y);
 
	pfsz.resize(n+1);
	for (int i = 0;i < n;++i) {
		sort(AI(xup[i]));
		xup[i].erase(unique(AI(xup[i])), end(xup[i]));
		while (xup[i].size() && xup[i].back() > h[i])
			xup[i].pop_back();
 
		pfsz[i+1] = pfsz[i] + xup[i].size();
		for (int j = 1;j < xup[i].size();++j) {
			int a = pfsz[i]+j-1, b = pfsz[i] + j
			//int a = get_id(i, xup[i][j-1]), b = get_id(i, xup[i][j]),
				, d = xup[i][j] - xup[i][j-1];
			edge[a].pb(b, d);
			edge[b].pb(a, d);
		}
	}
}
 
void mbuild(vector<int> l, vector<int> r, vector<int> y) {
 
	map<int, vector<int>> xs;
 
	for (int i = 0;i < n;++i) {
		for (int j : xup[i])
			xs[j].pb(i);
	}
 
	for (int i = 0;i < m;++i) {
		vector< int > loc;
 
		auto it = lower_bound(AI( xs[y[i]] ), l[i]);
		while (it != end(xs[y[i]])) {
			if (*it > r[i]) break;
			loc.pb(*it++);
		}
 
		for (int j = 1;j < loc.size();++j) {
			int a = get_id(loc[j-1], y[i]), b = get_id(loc[j], y[i]),
				d = x[ loc[j] ] - x[ loc[j-1] ];
		
			edge[a].pb(b, d);
			edge[b].pb(a, d);
		}
	}
}
 
ll sho(int s, int t) {
	int V = pfsz.back() + 10;
	vector<ll> dis(V, inf);
	
	priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
	auto upd = [&](int id, ll d) {
		if (chmin(dis[id], d))
			pq.emplace(d, id);
	};
 
	upd(s, 0);
 
	while (pq.size()) {
		auto [d, x] = pq.top(); pq.pop();
		if (d != dis[x]) continue;
		if (x == t) return d;
		DE(x, d);
		for (auto [u, w] : edge[x])
			upd(u, d + w);
	}
	return -1;
 
}
 
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 s, int g) {
	n = x.size();
	m = l.size();
	::x = x;
	::h = h;
 
	init_ver(l, r, y, s, g);
 
	mbuild(l, r, y);
 
	return sho( get_id(s, 0), get_id(g, 0) );
}

Compilation message (stderr)

walk.cpp: In function 'void sweep(std::vector<int>, std::vector<int>, std::vector<int>)':
walk.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
walk.cpp:43:3: note: in expansion of macro 'DE'
   43 |   DE(l[i], r[i], y[i]);
      |   ^~
walk.cpp: In function 'void init_ver(std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for (int j = 1;j < xup[i].size();++j) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void mbuild(std::vector<int>, std::vector<int>, std::vector<int>)':
walk.cpp:141:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for (int j = 1;j < loc.size();++j) {
      |                  ~~^~~~~~~~~~~~
walk.cpp: In function 'll sho(int, int)':
walk.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
walk.cpp:167:3: note: in expansion of macro 'DE'
  167 |   DE(x, d);
      |   ^~

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