oj.uz

Submission #815197

# Submission time Handle Problem Language Result Execution time Memory
815197 2023-08-08T13:07:55 Z ymm Sky Walking (IOI19_walk) C++17
43 / 100
 264 ms 39772 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, min(s, r+1), h);
			vector<int> vec = seg::get(l, min(s, r+1), 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(max(g+1, l), r+1, h);
			vector<int> vec = seg::get(max(g+1, l), 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 7 ms 15072 KB Output is correct
3 Correct 7 ms 15184 KB Output is correct
4 Correct 7 ms 15184 KB Output is correct
5 Correct 7 ms 15188 KB Output is correct
6 Correct 7 ms 15188 KB Output is correct
7 Correct 7 ms 15180 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 7 ms 15160 KB Output is correct
10 Correct 7 ms 15192 KB Output is correct
11 Correct 7 ms 15188 KB Output is correct
12 Correct 7 ms 15188 KB Output is correct
13 Correct 7 ms 15188 KB Output is correct
14 Correct 7 ms 15120 KB Output is correct
15 Correct 8 ms 15184 KB Output is correct
16 Correct 7 ms 15180 KB Output is correct
17 Correct 7 ms 15180 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15312 KB Output is correct
2 Correct 7 ms 15184 KB Output is correct
3 Correct 169 ms 32584 KB Output is correct
4 Correct 214 ms 36828 KB Output is correct
5 Correct 126 ms 32288 KB Output is correct
6 Correct 134 ms 31996 KB Output is correct
7 Correct 124 ms 32356 KB Output is correct
8 Correct 171 ms 33060 KB Output is correct
9 Correct 186 ms 35516 KB Output is correct
10 Correct 214 ms 37700 KB Output is correct
11 Correct 164 ms 31992 KB Output is correct
12 Correct 176 ms 31296 KB Output is correct
13 Correct 212 ms 37820 KB Output is correct
14 Correct 146 ms 31964 KB Output is correct
15 Incorrect 145 ms 32596 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 22660 KB Output is correct
2 Correct 163 ms 34088 KB Output is correct
3 Correct 190 ms 35164 KB Output is correct
4 Correct 263 ms 38892 KB Output is correct
5 Correct 251 ms 38896 KB Output is correct
6 Correct 245 ms 37700 KB Output is correct
7 Correct 127 ms 30152 KB Output is correct
8 Correct 179 ms 29888 KB Output is correct
9 Correct 222 ms 36580 KB Output is correct
10 Correct 134 ms 32312 KB Output is correct
11 Correct 22 ms 17740 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 22660 KB Output is correct
2 Correct 163 ms 34088 KB Output is correct
3 Correct 190 ms 35164 KB Output is correct
4 Correct 263 ms 38892 KB Output is correct
5 Correct 251 ms 38896 KB Output is correct
6 Correct 245 ms 37700 KB Output is correct
7 Correct 127 ms 30152 KB Output is correct
8 Correct 179 ms 29888 KB Output is correct
9 Correct 222 ms 36580 KB Output is correct
10 Correct 134 ms 32312 KB Output is correct
11 Correct 22 ms 17740 KB Output is correct
12 Correct 201 ms 35116 KB Output is correct
13 Correct 261 ms 39332 KB Output is correct
14 Correct 264 ms 39772 KB Output is correct
15 Correct 177 ms 36036 KB Output is correct
16 Correct 203 ms 37360 KB Output is correct
17 Correct 199 ms 38512 KB Output is correct
18 Correct 178 ms 35992 KB Output is correct
19 Correct 172 ms 35288 KB Output is correct
20 Correct 133 ms 30400 KB Output is correct
21 Correct 36 ms 20804 KB Output is correct
22 Correct 174 ms 35524 KB Output is correct
23 Correct 161 ms 34892 KB Output is correct
24 Correct 165 ms 31176 KB Output is correct
25 Correct 156 ms 33568 KB Output is correct
26 Correct 155 ms 29328 KB Output is correct
27 Correct 247 ms 39612 KB Output is correct
28 Correct 242 ms 39284 KB Output is correct
29 Correct 249 ms 38044 KB Output is correct
30 Correct 133 ms 30516 KB Output is correct
31 Correct 214 ms 36732 KB Output is correct
32 Correct 149 ms 31244 KB Output is correct
33 Correct 138 ms 30984 KB Output is correct
34 Correct 147 ms 32584 KB Output is correct
35 Correct 178 ms 32312 KB Output is correct
36 Correct 143 ms 31768 KB Output is correct
37 Correct 127 ms 30100 KB Output is correct
38 Correct 133 ms 29692 KB Output is correct
39 Correct 143 ms 32844 KB Output is correct
40 Correct 150 ms 30076 KB Output is correct
41 Correct 133 ms 30880 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 7 ms 15072 KB Output is correct
3 Correct 7 ms 15184 KB Output is correct
4 Correct 7 ms 15184 KB Output is correct
5 Correct 7 ms 15188 KB Output is correct
6 Correct 7 ms 15188 KB Output is correct
7 Correct 7 ms 15180 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 7 ms 15160 KB Output is correct
10 Correct 7 ms 15192 KB Output is correct
11 Correct 7 ms 15188 KB Output is correct
12 Correct 7 ms 15188 KB Output is correct
13 Correct 7 ms 15188 KB Output is correct
14 Correct 7 ms 15120 KB Output is correct
15 Correct 8 ms 15184 KB Output is correct
16 Correct 7 ms 15180 KB Output is correct
17 Correct 7 ms 15180 KB Output is correct
18 Correct 7 ms 15312 KB Output is correct
19 Correct 7 ms 15184 KB Output is correct
20 Correct 169 ms 32584 KB Output is correct
21 Correct 214 ms 36828 KB Output is correct
22 Correct 126 ms 32288 KB Output is correct
23 Correct 134 ms 31996 KB Output is correct
24 Correct 124 ms 32356 KB Output is correct
25 Correct 171 ms 33060 KB Output is correct
26 Correct 186 ms 35516 KB Output is correct
27 Correct 214 ms 37700 KB Output is correct
28 Correct 164 ms 31992 KB Output is correct
29 Correct 176 ms 31296 KB Output is correct
30 Correct 212 ms 37820 KB Output is correct
31 Correct 146 ms 31964 KB Output is correct
32 Incorrect 145 ms 32596 KB Output isn't correct
33 Halted 0 ms 0 KB -