oj.uz

Submission #814863

# Submission time Handle Problem Language Result Execution time Memory
814863 2023-08-08T10:44:59 Z ymm Sky Walking (IOI19_walk) C++17
25 / 100
 4000 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);
				}
			}
		}
	}
}


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);
	}
	spfa(&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 7 ms 15196 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 8 ms 15188 KB Output is correct
8 Correct 8 ms 15188 KB Output is correct
9 Correct 7 ms 15188 KB Output is correct
10 Correct 7 ms 15188 KB Output is correct
11 Correct 7 ms 15132 KB Output is correct
12 Correct 7 ms 15188 KB Output is correct
13 Correct 7 ms 15092 KB Output is correct
14 Correct 7 ms 15184 KB Output is correct
15 Correct 7 ms 15188 KB Output is correct
16 Correct 7 ms 15188 KB Output is correct
17 Correct 8 ms 15128 KB Output is correct

Subtask #2
0 / 14.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 Runtime error 1718 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 179 ms 22264 KB Output is correct
2 Correct 148 ms 34140 KB Output is correct
3 Correct 176 ms 35140 KB Output is correct
4 Correct 242 ms 38548 KB Output is correct
5 Correct 279 ms 38828 KB Output is correct
6 Correct 216 ms 37812 KB Output is correct
7 Correct 127 ms 29960 KB Output is correct
8 Correct 210 ms 29300 KB Output is correct
9 Correct 212 ms 36484 KB Output is correct
10 Correct 128 ms 30732 KB Output is correct
11 Correct 18 ms 17744 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 22264 KB Output is correct
2 Correct 148 ms 34140 KB Output is correct
3 Correct 176 ms 35140 KB Output is correct
4 Correct 242 ms 38548 KB Output is correct
5 Correct 279 ms 38828 KB Output is correct
6 Correct 216 ms 37812 KB Output is correct
7 Correct 127 ms 29960 KB Output is correct
8 Correct 210 ms 29300 KB Output is correct
9 Correct 212 ms 36484 KB Output is correct
10 Correct 128 ms 30732 KB Output is correct
11 Correct 18 ms 17744 KB Output is correct
12 Correct 196 ms 35276 KB Output is correct
13 Correct 271 ms 38864 KB Output is correct
14 Correct 256 ms 39460 KB Output is correct
15 Correct 178 ms 33632 KB Output is correct
16 Correct 201 ms 35400 KB Output is correct
17 Correct 185 ms 36296 KB Output is correct
18 Correct 165 ms 33988 KB Output is correct
19 Correct 171 ms 34500 KB Output is correct
20 Correct 134 ms 30556 KB Output is correct
21 Correct 30 ms 20804 KB Output is correct
22 Correct 167 ms 35180 KB Output is correct
23 Correct 159 ms 34504 KB Output is correct
24 Correct 183 ms 31224 KB Output is correct
25 Correct 170 ms 33852 KB Output is correct
26 Correct 131 ms 29612 KB Output is correct
27 Correct 247 ms 40516 KB Output is correct
28 Correct 2144 ms 41456 KB Output is correct
29 Correct 250 ms 39548 KB Output is correct
30 Correct 121 ms 30800 KB Output is correct
31 Correct 222 ms 38376 KB Output is correct
32 Correct 127 ms 31100 KB Output is correct
33 Correct 133 ms 31188 KB Output is correct
34 Correct 126 ms 32576 KB Output is correct
35 Correct 154 ms 32908 KB Output is correct
36 Execution timed out 4021 ms 32216 KB Time limit exceeded
37 Halted 0 ms 0 KB -

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 7 ms 15196 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 8 ms 15188 KB Output is correct
8 Correct 8 ms 15188 KB Output is correct
9 Correct 7 ms 15188 KB Output is correct
10 Correct 7 ms 15188 KB Output is correct
11 Correct 7 ms 15132 KB Output is correct
12 Correct 7 ms 15188 KB Output is correct
13 Correct 7 ms 15092 KB Output is correct
14 Correct 7 ms 15184 KB Output is correct
15 Correct 7 ms 15188 KB Output is correct
16 Correct 7 ms 15188 KB Output is correct
17 Correct 8 ms 15128 KB Output is correct
18 Correct 7 ms 15188 KB Output is correct
19 Correct 7 ms 15188 KB Output is correct
20 Runtime error 1718 ms 1048576 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -