oj.uz

Submission #815003

# Submission time Handle Problem Language Result Execution time Memory
815003 2023-08-08T11:38:42 Z ymm Sky Walking (IOI19_walk) C++17
43 / 100
 1739 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()) {
		assert(S.size() < N);
		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 8 ms 15180 KB Output is correct
2 Correct 9 ms 15076 KB Output is correct
3 Correct 8 ms 15180 KB Output is correct
4 Correct 7 ms 15188 KB Output is correct
5 Correct 8 ms 15188 KB Output is correct
6 Correct 7 ms 15184 KB Output is correct
7 Correct 7 ms 15188 KB Output is correct
8 Correct 8 ms 15104 KB Output is correct
9 Correct 7 ms 15188 KB Output is correct
10 Correct 7 ms 15180 KB Output is correct
11 Correct 7 ms 15184 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 15180 KB Output is correct
15 Correct 7 ms 15184 KB Output is correct
16 Correct 7 ms 15188 KB Output is correct
17 Correct 8 ms 15188 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15136 KB Output is correct
2 Correct 7 ms 15188 KB Output is correct
3 Runtime error 1739 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 96 ms 22216 KB Output is correct
2 Correct 160 ms 32632 KB Output is correct
3 Correct 198 ms 33376 KB Output is correct
4 Correct 240 ms 36680 KB Output is correct
5 Correct 244 ms 36584 KB Output is correct
6 Correct 226 ms 35524 KB Output is correct
7 Correct 121 ms 27920 KB Output is correct
8 Correct 198 ms 27624 KB Output is correct
9 Correct 216 ms 34332 KB Output is correct
10 Correct 138 ms 30056 KB Output is correct
11 Correct 20 ms 17260 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 22216 KB Output is correct
2 Correct 160 ms 32632 KB Output is correct
3 Correct 198 ms 33376 KB Output is correct
4 Correct 240 ms 36680 KB Output is correct
5 Correct 244 ms 36584 KB Output is correct
6 Correct 226 ms 35524 KB Output is correct
7 Correct 121 ms 27920 KB Output is correct
8 Correct 198 ms 27624 KB Output is correct
9 Correct 216 ms 34332 KB Output is correct
10 Correct 138 ms 30056 KB Output is correct
11 Correct 20 ms 17260 KB Output is correct
12 Correct 189 ms 33448 KB Output is correct
13 Correct 249 ms 36644 KB Output is correct
14 Correct 242 ms 36752 KB Output is correct
15 Correct 181 ms 32700 KB Output is correct
16 Correct 202 ms 33756 KB Output is correct
17 Correct 176 ms 34912 KB Output is correct
18 Correct 172 ms 32708 KB Output is correct
19 Correct 173 ms 31716 KB Output is correct
20 Correct 130 ms 27916 KB Output is correct
21 Correct 30 ms 19348 KB Output is correct
22 Correct 159 ms 32288 KB Output is correct
23 Correct 153 ms 31528 KB Output is correct
24 Correct 146 ms 28084 KB Output is correct
25 Correct 147 ms 30632 KB Output is correct
26 Correct 158 ms 26320 KB Output is correct
27 Correct 242 ms 36616 KB Output is correct
28 Correct 231 ms 36548 KB Output is correct
29 Correct 229 ms 35528 KB Output is correct
30 Correct 115 ms 27868 KB Output is correct
31 Correct 201 ms 34348 KB Output is correct
32 Correct 129 ms 28900 KB Output is correct
33 Correct 125 ms 28756 KB Output is correct
34 Correct 135 ms 30264 KB Output is correct
35 Correct 147 ms 30016 KB Output is correct
36 Correct 146 ms 29388 KB Output is correct
37 Correct 122 ms 27728 KB Output is correct
38 Correct 121 ms 27396 KB Output is correct
39 Correct 130 ms 30472 KB Output is correct
40 Correct 140 ms 27852 KB Output is correct
41 Correct 146 ms 28648 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15180 KB Output is correct
2 Correct 9 ms 15076 KB Output is correct
3 Correct 8 ms 15180 KB Output is correct
4 Correct 7 ms 15188 KB Output is correct
5 Correct 8 ms 15188 KB Output is correct
6 Correct 7 ms 15184 KB Output is correct
7 Correct 7 ms 15188 KB Output is correct
8 Correct 8 ms 15104 KB Output is correct
9 Correct 7 ms 15188 KB Output is correct
10 Correct 7 ms 15180 KB Output is correct
11 Correct 7 ms 15184 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 15180 KB Output is correct
15 Correct 7 ms 15184 KB Output is correct
16 Correct 7 ms 15188 KB Output is correct
17 Correct 8 ms 15188 KB Output is correct
18 Correct 7 ms 15136 KB Output is correct
19 Correct 7 ms 15188 KB Output is correct
20 Runtime error 1739 ms 1048576 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -