oj.uz

Submission #814894

# Submission time Handle Problem Language Result Execution time Memory
814894 2023-08-08T10:57:44 Z ymm Sky Walking (IOI19_walk) C++17
43 / 100
 1502 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 = 400'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 27 ms 59732 KB Output is correct
2 Correct 28 ms 59732 KB Output is correct
3 Correct 30 ms 59732 KB Output is correct
4 Correct 29 ms 59752 KB Output is correct
5 Correct 28 ms 59784 KB Output is correct
6 Correct 30 ms 59760 KB Output is correct
7 Correct 29 ms 59736 KB Output is correct
8 Correct 30 ms 59724 KB Output is correct
9 Correct 29 ms 59780 KB Output is correct
10 Correct 30 ms 59776 KB Output is correct
11 Correct 29 ms 59804 KB Output is correct
12 Correct 29 ms 59700 KB Output is correct
13 Correct 29 ms 59732 KB Output is correct
14 Correct 29 ms 59716 KB Output is correct
15 Correct 29 ms 59740 KB Output is correct
16 Correct 29 ms 59732 KB Output is correct
17 Correct 29 ms 59732 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 59724 KB Output is correct
2 Correct 31 ms 59760 KB Output is correct
3 Runtime error 1502 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 83 ms 67184 KB Output is correct
2 Correct 193 ms 77464 KB Output is correct
3 Correct 212 ms 78176 KB Output is correct
4 Correct 256 ms 81340 KB Output is correct
5 Correct 258 ms 81452 KB Output is correct
6 Correct 242 ms 80176 KB Output is correct
7 Correct 138 ms 72696 KB Output is correct
8 Correct 192 ms 72480 KB Output is correct
9 Correct 224 ms 79104 KB Output is correct
10 Correct 152 ms 74784 KB Output is correct
11 Correct 38 ms 62024 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 67184 KB Output is correct
2 Correct 193 ms 77464 KB Output is correct
3 Correct 212 ms 78176 KB Output is correct
4 Correct 256 ms 81340 KB Output is correct
5 Correct 258 ms 81452 KB Output is correct
6 Correct 242 ms 80176 KB Output is correct
7 Correct 138 ms 72696 KB Output is correct
8 Correct 192 ms 72480 KB Output is correct
9 Correct 224 ms 79104 KB Output is correct
10 Correct 152 ms 74784 KB Output is correct
11 Correct 38 ms 62024 KB Output is correct
12 Correct 209 ms 78284 KB Output is correct
13 Correct 258 ms 81948 KB Output is correct
14 Correct 256 ms 81940 KB Output is correct
15 Correct 204 ms 78060 KB Output is correct
16 Correct 201 ms 78928 KB Output is correct
17 Correct 202 ms 80048 KB Output is correct
18 Correct 197 ms 77820 KB Output is correct
19 Correct 184 ms 76876 KB Output is correct
20 Correct 155 ms 73092 KB Output is correct
21 Correct 50 ms 64564 KB Output is correct
22 Correct 184 ms 77464 KB Output is correct
23 Correct 181 ms 76712 KB Output is correct
24 Correct 163 ms 73228 KB Output is correct
25 Correct 175 ms 75896 KB Output is correct
26 Correct 154 ms 71592 KB Output is correct
27 Correct 261 ms 81836 KB Output is correct
28 Correct 264 ms 81848 KB Output is correct
29 Correct 242 ms 80612 KB Output is correct
30 Correct 139 ms 73008 KB Output is correct
31 Correct 230 ms 79224 KB Output is correct
32 Correct 151 ms 73828 KB Output is correct
33 Correct 150 ms 73556 KB Output is correct
34 Correct 162 ms 75128 KB Output is correct
35 Correct 175 ms 74812 KB Output is correct
36 Correct 166 ms 74380 KB Output is correct
37 Correct 144 ms 72644 KB Output is correct
38 Correct 152 ms 72176 KB Output is correct
39 Correct 145 ms 75296 KB Output is correct
40 Correct 149 ms 72628 KB Output is correct
41 Correct 152 ms 73536 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 59732 KB Output is correct
2 Correct 28 ms 59732 KB Output is correct
3 Correct 30 ms 59732 KB Output is correct
4 Correct 29 ms 59752 KB Output is correct
5 Correct 28 ms 59784 KB Output is correct
6 Correct 30 ms 59760 KB Output is correct
7 Correct 29 ms 59736 KB Output is correct
8 Correct 30 ms 59724 KB Output is correct
9 Correct 29 ms 59780 KB Output is correct
10 Correct 30 ms 59776 KB Output is correct
11 Correct 29 ms 59804 KB Output is correct
12 Correct 29 ms 59700 KB Output is correct
13 Correct 29 ms 59732 KB Output is correct
14 Correct 29 ms 59716 KB Output is correct
15 Correct 29 ms 59740 KB Output is correct
16 Correct 29 ms 59732 KB Output is correct
17 Correct 29 ms 59732 KB Output is correct
18 Correct 29 ms 59724 KB Output is correct
19 Correct 31 ms 59760 KB Output is correct
20 Runtime error 1502 ms 1048576 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -