oj.uz

Submission #815032

# Submission time Handle Problem Language Result Execution time Memory
815032 2023-08-08T11:51:29 Z ymm Sky Walking (IOI19_walk) C++17
43 / 100
 1448 ms 1031332 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()) {
		assert(clock() < CLOCKS_PER_SEC);
		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 7 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 15164 KB Output is correct
6 Correct 7 ms 15188 KB Output is correct
7 Correct 7 ms 15152 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 7 ms 15188 KB Output is correct
10 Correct 6 ms 15188 KB Output is correct
11 Correct 8 ms 15188 KB Output is correct
12 Correct 8 ms 15188 KB Output is correct
13 Correct 7 ms 15196 KB Output is correct
14 Correct 7 ms 15188 KB Output is correct
15 Correct 7 ms 15188 KB Output is correct
16 Correct 7 ms 15128 KB Output is correct
17 Correct 7 ms 15188 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 21932 KB Output is correct
2 Correct 178 ms 32364 KB Output is correct
3 Correct 230 ms 33032 KB Output is correct
4 Correct 265 ms 36272 KB Output is correct
5 Correct 274 ms 36188 KB Output is correct
6 Correct 243 ms 35048 KB Output is correct
7 Correct 130 ms 27528 KB Output is correct
8 Correct 198 ms 27308 KB Output is correct
9 Correct 225 ms 33980 KB Output is correct
10 Correct 154 ms 29752 KB Output is correct
11 Correct 16 ms 16984 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 21932 KB Output is correct
2 Correct 178 ms 32364 KB Output is correct
3 Correct 230 ms 33032 KB Output is correct
4 Correct 265 ms 36272 KB Output is correct
5 Correct 274 ms 36188 KB Output is correct
6 Correct 243 ms 35048 KB Output is correct
7 Correct 130 ms 27528 KB Output is correct
8 Correct 198 ms 27308 KB Output is correct
9 Correct 225 ms 33980 KB Output is correct
10 Correct 154 ms 29752 KB Output is correct
11 Correct 16 ms 16984 KB Output is correct
12 Correct 209 ms 32964 KB Output is correct
13 Correct 283 ms 36256 KB Output is correct
14 Correct 267 ms 36184 KB Output is correct
15 Correct 245 ms 32184 KB Output is correct
16 Correct 284 ms 33228 KB Output is correct
17 Correct 205 ms 34396 KB Output is correct
18 Correct 196 ms 32216 KB Output is correct
19 Correct 186 ms 31220 KB Output is correct
20 Correct 152 ms 27412 KB Output is correct
21 Correct 34 ms 18888 KB Output is correct
22 Correct 183 ms 31808 KB Output is correct
23 Correct 192 ms 31060 KB Output is correct
24 Correct 162 ms 27608 KB Output is correct
25 Correct 171 ms 30268 KB Output is correct
26 Correct 180 ms 25900 KB Output is correct
27 Correct 282 ms 36208 KB Output is correct
28 Correct 267 ms 36068 KB Output is correct
29 Correct 248 ms 35036 KB Output is correct
30 Correct 131 ms 27564 KB Output is correct
31 Correct 235 ms 33988 KB Output is correct
32 Correct 153 ms 28556 KB Output is correct
33 Correct 150 ms 28388 KB Output is correct
34 Correct 189 ms 29908 KB Output is correct
35 Correct 185 ms 29616 KB Output is correct
36 Correct 185 ms 28960 KB Output is correct
37 Correct 150 ms 27312 KB Output is correct
38 Correct 157 ms 26960 KB Output is correct
39 Correct 153 ms 30144 KB Output is correct
40 Correct 150 ms 27340 KB Output is correct
41 Correct 174 ms 28268 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 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 15164 KB Output is correct
6 Correct 7 ms 15188 KB Output is correct
7 Correct 7 ms 15152 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 7 ms 15188 KB Output is correct
10 Correct 6 ms 15188 KB Output is correct
11 Correct 8 ms 15188 KB Output is correct
12 Correct 8 ms 15188 KB Output is correct
13 Correct 7 ms 15196 KB Output is correct
14 Correct 7 ms 15188 KB Output is correct
15 Correct 7 ms 15188 KB Output is correct
16 Correct 7 ms 15128 KB Output is correct
17 Correct 7 ms 15188 KB Output is correct
18 Correct 8 ms 15188 KB Output is correct
19 Correct 7 ms 15188 KB Output is correct
20 Runtime error 1448 ms 1031332 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -