oj.uz

Submission #815010

# Submission time Handle Problem Language Result Execution time Memory
815010 2023-08-08T11:42:06 Z ymm Sky Walking (IOI19_walk) C++17
43 / 100
 1663 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()) {
		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);
	}
	assert(clock() < CLOCKS_PER_SEC);
	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 7 ms 15188 KB Output is correct
4 Correct 6 ms 15188 KB Output is correct
5 Correct 7 ms 15184 KB Output is correct
6 Correct 7 ms 15180 KB Output is correct
7 Correct 7 ms 15188 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 7 ms 15184 KB Output is correct
10 Correct 7 ms 15188 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 15072 KB Output is correct
14 Correct 7 ms 15180 KB Output is correct
15 Correct 8 ms 15172 KB Output is correct
16 Correct 7 ms 15188 KB Output is correct
17 Correct 8 ms 15180 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 1663 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 61 ms 21936 KB Output is correct
2 Correct 149 ms 32304 KB Output is correct
3 Correct 184 ms 33052 KB Output is correct
4 Correct 250 ms 36252 KB Output is correct
5 Correct 229 ms 36188 KB Output is correct
6 Correct 213 ms 35140 KB Output is correct
7 Correct 113 ms 27612 KB Output is correct
8 Correct 181 ms 27244 KB Output is correct
9 Correct 202 ms 34116 KB Output is correct
10 Correct 125 ms 29764 KB Output is correct
11 Correct 16 ms 16968 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 21936 KB Output is correct
2 Correct 149 ms 32304 KB Output is correct
3 Correct 184 ms 33052 KB Output is correct
4 Correct 250 ms 36252 KB Output is correct
5 Correct 229 ms 36188 KB Output is correct
6 Correct 213 ms 35140 KB Output is correct
7 Correct 113 ms 27612 KB Output is correct
8 Correct 181 ms 27244 KB Output is correct
9 Correct 202 ms 34116 KB Output is correct
10 Correct 125 ms 29764 KB Output is correct
11 Correct 16 ms 16968 KB Output is correct
12 Correct 183 ms 33068 KB Output is correct
13 Correct 228 ms 36312 KB Output is correct
14 Correct 229 ms 36184 KB Output is correct
15 Correct 173 ms 32204 KB Output is correct
16 Correct 182 ms 33388 KB Output is correct
17 Correct 175 ms 34356 KB Output is correct
18 Correct 168 ms 32232 KB Output is correct
19 Correct 165 ms 31156 KB Output is correct
20 Correct 126 ms 27408 KB Output is correct
21 Correct 26 ms 18892 KB Output is correct
22 Correct 160 ms 31792 KB Output is correct
23 Correct 150 ms 31072 KB Output is correct
24 Correct 147 ms 27572 KB Output is correct
25 Correct 148 ms 30276 KB Output is correct
26 Correct 131 ms 25948 KB Output is correct
27 Correct 229 ms 36168 KB Output is correct
28 Correct 229 ms 36092 KB Output is correct
29 Correct 224 ms 35076 KB Output is correct
30 Correct 120 ms 27576 KB Output is correct
31 Correct 203 ms 33984 KB Output is correct
32 Correct 126 ms 28564 KB Output is correct
33 Correct 122 ms 28312 KB Output is correct
34 Correct 131 ms 29880 KB Output is correct
35 Correct 156 ms 29632 KB Output is correct
36 Correct 143 ms 28932 KB Output is correct
37 Correct 119 ms 27328 KB Output is correct
38 Correct 131 ms 26948 KB Output is correct
39 Correct 133 ms 30440 KB Output is correct
40 Correct 125 ms 27336 KB Output is correct
41 Correct 128 ms 28272 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 7 ms 15188 KB Output is correct
4 Correct 6 ms 15188 KB Output is correct
5 Correct 7 ms 15184 KB Output is correct
6 Correct 7 ms 15180 KB Output is correct
7 Correct 7 ms 15188 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 7 ms 15184 KB Output is correct
10 Correct 7 ms 15188 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 15072 KB Output is correct
14 Correct 7 ms 15180 KB Output is correct
15 Correct 8 ms 15172 KB Output is correct
16 Correct 7 ms 15188 KB Output is correct
17 Correct 8 ms 15180 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 1663 ms 1048576 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -