답안 #815045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
815045 2023-08-08T11:58:47 Z ymm Sky Walking (IOI19_walk) C++17
0 / 100
61 ms 39596 KB
#include "walk.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;

struct node {
	vector<pair<node *, ll>> a;
	bool vis;
	ll dis;
};

struct {
	node lp, mp, rp;
	int lpr, mpl, mpr, rpl;
	int l, r, h;
} walk[N];

namespace seg {
	int mx[N*4];
	int t[N*4];
	int sz;
	
	void get(int l, int r, int h, vector<int> &ans, int i, int b, int e) {
		if (r <= b || e <= l || mx[i] < h || t[i] == -2)
			return;
		if (l <= b && e <= r && t[i] != -1) {
			if (ans.empty() || ans.back() != t[i])
				ans.push_back(t[i]);
			return;
		}
		if (t[i] != -1)
			t[2*i+1] = t[2*i+2] = t[i];
		get(l, r, h, ans, 2*i+1, b, (b+e)/2);
		get(l, r, h, ans, 2*i+2, (b+e)/2, e);
	}
	vector<int> get(int l, int r, int h) {
		vector<int> ans;
		get(l, r, h, ans, 0, 0, sz);
		return ans;
	}

	void up(int l, int r, int x, int i, int b, int e) {
		if (l <= b && e <= r) {
			t[i] = x;
			return;
		}
		if (r <= b || e <= l)
			return;
		if (t[i] != -1)
			t[2*i+1] = t[2*i+2] = t[i];
		up(l, r, x, 2*i+1, b, (b+e)/2);
		up(l, r, x, 2*i+2, (b+e)/2, e);
		t[i] = t[2*i+1] == t[2*i+2]? t[2*i+1]: -1;
	}
	void up(int l, int r, int x) { up(l, r, x, 0, 0, sz); }

	int lrmost(int l, int r, bool d, int h, int i, int b, int e) {
		if (mx[i] < h || r <= b || e <= l)
			return -1;
		if (e-b == 1)
			return b;
		int x;
		if ((x = lrmost(l, r, d, h, 2*i+1+ d, d? (b+e)/2: b, d? e: (b+e)/2)) != -1)
			return x;
		if ((x = lrmost(l, r, d, h, 2*i+1+!d, d? b: (b+e)/2, d? (b+e)/2: e)) != -1)
			return x;
		return -1;
	}
	int leftmost(int l, int r, int h) { return lrmost(l, r, 0, h, 0, 0, sz); }
	int rightmost(int l, int r, int h) { return lrmost(l, r, 1, h, 0, 0, sz); }

	void init(const vector<int> &vec, int i, int b, int e) {
		t[i] = -2;
		if (e-b == 1) {
			mx[i] = vec[b];
			return;
		}
		init(vec, 2*i+1, b, (b+e)/2);
		init(vec, 2*i+2, (b+e)/2, e);
		mx[i] = max(mx[2*i+1], mx[2*i+2]);
	}
	void init(const vector<int> &vec) {
		sz = vec.size();
		init(vec, 0, 0, sz);
	}
}

pii get_walk(node *v)
{
	long vi = (long)(void *)v;
	long wi = (long)(void *)walk;
	long x = (vi - wi)/sizeof(*walk);
	long y = (vi - wi)%sizeof(*walk);
	y /= sizeof(node);
	return {x, y};
}

void spfa(node *s)
{
	s->dis = 0;
	s->vis = 1;
	vector<node *> q1 = {s}, q2;
	for (int i = 0;; ++i) {
		if (i == q1.size()) {
			if (q2.empty())
				break;
			q1.clear();
			q1.swap(q2);
			i = 0;
		}
		node *v = q1[i];
		v->vis = 0;
		for (auto [u, w] : v->a) {
			if (v->dis + w < u->dis) {
				u->dis = v->dis + w;
				if (!u->vis) {
					u->vis = 1;
					q2.push_back(u);
				}
			}
		}
	}
}

void dij(node *s)
{
	s->dis = 0;
	set<pair<ll, node *>> S;
	S.insert({0, s});
	while (S.size()) {
		auto [d, v] = *S.begin();
		S.erase(S.begin());
		for (auto [u, w] : v->a) {
			if (d + w < u->dis) {
				S.erase({u->dis, u});
				u->dis = d+w;
				S.insert({u->dis, u});
			}
		}
	}
}


long long min_distance(std::vector<int> pos, std::vector<int> height, std::vector<int> l, std::vector<int> r, std::vector<int> h, int s, int g) {
	if (s > g)
		swap(s, g);
	vector<tuple<int,int,int>> w;
	Loop (i,0,h.size())
		w.emplace_back(h[i], l[i], r[i]);
	w.emplace_back(0, s, s);
	w.emplace_back(0, g, g);
	sort(w.begin(), w.end());
	seg::init(height);
	int cnt[3] = {};
	Loop (i,0,w.size()) {
		auto [h, l, r] = w[i];
		walk[i].l = l;
		walk[i].r = r;
		walk[i].h = h;
		bool hl = 0, hm = 0, hr = 0;
		if (l < s) {
			hl = 1;
			walk[i].lpr = seg::rightmost(l, s, h);
			vector<int> vec = seg::get(l, s, h);
			assert(vec.size() <= cnt[0]);
			cnt[0] -= max((int)vec.size() - 2, 0);
			cnt[0] += 1;
			for (int j : vec) {
				walk[i].lp.a.emplace_back(&walk[j].lp, 2ll*(pos[walk[i].lpr] - pos[walk[j].lpr]) + abs(walk[i].h - walk[j].h));
				walk[j].lp.a.emplace_back(&walk[i].lp, 2ll*(pos[walk[j].lpr] - pos[walk[i].lpr]) + abs(walk[i].h - walk[j].h));
			}
		}
		if (l <= g || s <= r) {
			int ls = max(l, s);
			int rs = min(r, g)+1;
			walk[i].mpl = seg::leftmost(ls, rs, h);
			walk[i].mpr = seg::rightmost(ls, rs, h);
			vector<int> vec = seg::get(ls, rs, h);
			assert(vec.size() <= cnt[1]);
			cnt[1] -= max((int)vec.size() - 2, 0);
			cnt[1] += 1;
			hm = vec.size();
			for (int j : vec) {
				walk[i].mp.a.emplace_back(&walk[j].mp, abs(walk[i].h - walk[j].h));
				walk[j].mp.a.emplace_back(&walk[i].mp, abs(walk[i].h - walk[j].h));
			}
		}
		if (g < r) {
			hr = 1;
			walk[i].rpl = seg::leftmost(g+1, r+1, h);
			vector<int> vec = seg::get(g+1, r+1, h);
			assert(vec.size() <= cnt[2]);
			cnt[2] -= max((int)vec.size() - 2, 0);
			cnt[2] += 1;
			for (int j : vec) {
				walk[i].rp.a.emplace_back(&walk[j].rp, 2ll*(pos[walk[j].rpl] - pos[walk[i].rpl]) + abs(walk[i].h - walk[j].h));
				walk[j].rp.a.emplace_back(&walk[i].rp, 2ll*(pos[walk[i].rpl] - pos[walk[j].rpl]) + abs(walk[i].h - walk[j].h));
			}
		}
		if (hl && hm) {
			walk[i].lp.a.emplace_back(&walk[i].mp, 2*(pos[walk[i].mpl] - pos[s]));
			walk[i].mp.a.emplace_back(&walk[i].lp, 2*(pos[s] - pos[walk[i].lpr]));
		}
		if (hl && hr && !hm) {
			walk[i].lp.a.emplace_back(&walk[i].rp, 2*(pos[walk[i].rpl] - pos[s]));
			walk[i].rp.a.emplace_back(&walk[i].lp, 2*(pos[s] - pos[walk[i].lpr]));
		}
		if (hm && hr) {
			walk[i].mp.a.emplace_back(&walk[i].rp, 2*(pos[walk[i].rpl] - pos[walk[i].mpr]));
			walk[i].rp.a.emplace_back(&walk[i].mp, 0);
		}
		walk[i].lp.dis = walk[i].mp.dis = walk[i].rp.dis = 1e18;
		seg::up(l, r+1, i);
	}
	dij(&walk[1].mp);
	if (walk[0].mp.dis >= (ll)1e18)
		return -1;
	return walk[0].mp.dis + pos[g] - pos[s];
}

Compilation message

walk.cpp: In function 'void spfa(node*)':
walk.cpp:110:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   if (i == q1.size()) {
      |       ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from walk.cpp:2:
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:171:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  171 |    assert(vec.size() <= cnt[0]);
      |           ~~~~~~~~~~~^~~~~~~~~
walk.cpp:185:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  185 |    assert(vec.size() <= cnt[1]);
      |           ~~~~~~~~~~~^~~~~~~~~
walk.cpp:198:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  198 |    assert(vec.size() <= cnt[2]);
      |           ~~~~~~~~~~~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15184 KB Output is correct
2 Correct 8 ms 15092 KB Output is correct
3 Correct 8 ms 15184 KB Output is correct
4 Correct 8 ms 15188 KB Output is correct
5 Correct 7 ms 15120 KB Output is correct
6 Correct 8 ms 15188 KB Output is correct
7 Runtime error 20 ms 30540 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 15176 KB Output is correct
2 Correct 7 ms 15188 KB Output is correct
3 Runtime error 59 ms 39596 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 22720 KB Output is correct
2 Runtime error 52 ms 39240 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 22720 KB Output is correct
2 Runtime error 52 ms 39240 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15184 KB Output is correct
2 Correct 8 ms 15092 KB Output is correct
3 Correct 8 ms 15184 KB Output is correct
4 Correct 8 ms 15188 KB Output is correct
5 Correct 7 ms 15120 KB Output is correct
6 Correct 8 ms 15188 KB Output is correct
7 Runtime error 20 ms 30540 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -