oj.uz

Submission #814883

# Submission time Handle Problem Language Result Execution time Memory
814883 2023-08-08T10:54:25 Z ymm Sky Walking (IOI19_walk) C++17
43 / 100
 1585 ms 1048576 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);
	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);
			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);
			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);
			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()) {
      |       ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 6 ms 15188 KB Output is correct
3 Correct 6 ms 15188 KB Output is correct
4 Correct 6 ms 15188 KB Output is correct
5 Correct 6 ms 15180 KB Output is correct
6 Correct 6 ms 15184 KB Output is correct
7 Correct 8 ms 15112 KB Output is correct
8 Correct 6 ms 15180 KB Output is correct
9 Correct 6 ms 15180 KB Output is correct
10 Correct 7 ms 15188 KB Output is correct
11 Correct 8 ms 15092 KB Output is correct
12 Correct 6 ms 15188 KB Output is correct
13 Correct 7 ms 15188 KB Output is correct
14 Correct 6 ms 15188 KB Output is correct
15 Correct 7 ms 15188 KB Output is correct
16 Correct 7 ms 15100 KB Output is correct
17 Correct 8 ms 15208 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15184 KB Output is correct
2 Correct 8 ms 15188 KB Output is correct
3 Runtime error 1585 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 22680 KB Output is correct
2 Correct 163 ms 33992 KB Output is correct
3 Correct 192 ms 35124 KB Output is correct
4 Correct 296 ms 40356 KB Output is correct
5 Correct 299 ms 40352 KB Output is correct
6 Correct 247 ms 39192 KB Output is correct
7 Correct 140 ms 30572 KB Output is correct
8 Correct 178 ms 31344 KB Output is correct
9 Correct 212 ms 37984 KB Output is correct
10 Correct 130 ms 33148 KB Output is correct
11 Correct 18 ms 17756 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 22680 KB Output is correct
2 Correct 163 ms 33992 KB Output is correct
3 Correct 192 ms 35124 KB Output is correct
4 Correct 296 ms 40356 KB Output is correct
5 Correct 299 ms 40352 KB Output is correct
6 Correct 247 ms 39192 KB Output is correct
7 Correct 140 ms 30572 KB Output is correct
8 Correct 178 ms 31344 KB Output is correct
9 Correct 212 ms 37984 KB Output is correct
10 Correct 130 ms 33148 KB Output is correct
11 Correct 18 ms 17756 KB Output is correct
12 Correct 201 ms 34880 KB Output is correct
13 Correct 242 ms 39800 KB Output is correct
14 Correct 247 ms 39276 KB Output is correct
15 Correct 208 ms 34840 KB Output is correct
16 Correct 199 ms 35776 KB Output is correct
17 Correct 195 ms 36592 KB Output is correct
18 Correct 198 ms 33980 KB Output is correct
19 Correct 180 ms 32968 KB Output is correct
20 Correct 149 ms 28392 KB Output is correct
21 Correct 37 ms 19908 KB Output is correct
22 Correct 165 ms 33008 KB Output is correct
23 Correct 184 ms 32300 KB Output is correct
24 Correct 195 ms 28528 KB Output is correct
25 Correct 172 ms 31036 KB Output is correct
26 Correct 164 ms 26668 KB Output is correct
27 Correct 244 ms 37024 KB Output is correct
28 Correct 243 ms 36696 KB Output is correct
29 Correct 221 ms 35528 KB Output is correct
30 Correct 119 ms 27972 KB Output is correct
31 Correct 215 ms 34156 KB Output is correct
32 Correct 132 ms 28676 KB Output is correct
33 Correct 130 ms 28464 KB Output is correct
34 Correct 135 ms 30040 KB Output is correct
35 Correct 159 ms 29708 KB Output is correct
36 Correct 159 ms 29200 KB Output is correct
37 Correct 135 ms 30092 KB Output is correct
38 Correct 127 ms 30084 KB Output is correct
39 Correct 145 ms 32944 KB Output is correct
40 Correct 155 ms 30368 KB Output is correct
41 Correct 133 ms 30916 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 6 ms 15188 KB Output is correct
3 Correct 6 ms 15188 KB Output is correct
4 Correct 6 ms 15188 KB Output is correct
5 Correct 6 ms 15180 KB Output is correct
6 Correct 6 ms 15184 KB Output is correct
7 Correct 8 ms 15112 KB Output is correct
8 Correct 6 ms 15180 KB Output is correct
9 Correct 6 ms 15180 KB Output is correct
10 Correct 7 ms 15188 KB Output is correct
11 Correct 8 ms 15092 KB Output is correct
12 Correct 6 ms 15188 KB Output is correct
13 Correct 7 ms 15188 KB Output is correct
14 Correct 6 ms 15188 KB Output is correct
15 Correct 7 ms 15188 KB Output is correct
16 Correct 7 ms 15100 KB Output is correct
17 Correct 8 ms 15208 KB Output is correct
18 Correct 7 ms 15184 KB Output is correct
19 Correct 8 ms 15188 KB Output is correct
20 Runtime error 1585 ms 1048576 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -