oj.uz

Submission #143104

# Submission time Handle Problem Language Result Execution time Memory
143104 2019-08-13T01:30:21 Z model_code Sky Walking (IOI19_walk) C++17
25 / 100
 4000 ms 49272 KB 
// incorrect/maroon-spfa.cpp

#include <bits/stdc++.h>
#include <type_traits>
#include "walk.h"

using namespace std;

using ll = int64_t;

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()
auto &errStream = cerr;
#ifdef LOCAL
#define cerr (cerr << "-- line " << __LINE__ << " -- ")
#else
class CerrDummy
{
} cerrDummy;
template <class T>
CerrDummy &operator<<(CerrDummy &cd, const T &)
{
	return cd;
}
using charTDummy = char;
using traitsDummy = char_traits<charTDummy>;
CerrDummy &operator<<(CerrDummy &cd, basic_ostream<charTDummy, traitsDummy> &(basic_ostream<charTDummy, traitsDummy> &))
{
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr << "reached" << endl
#define DMP(x) cerr << #x << ":" << x << endl
#define ZERO(x) memset(x, 0, sizeof(x))
#define ONE(x) memset(x, -1, sizeof(x))

using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
	os << "(" << p.first << "," << p.second << ")";
	return os;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
	os << "{";
	REP(i, (int)v.size())
	{
		if (i)
			os << ",";
		os << v[i];
	}
	os << "}";
	return os;
}

ll read()
{
	ll i;
	scanf("%" SCNd64, &i);
	return i;
}

void printSpace()
{
	printf(" ");
}

void printEoln()
{
	printf("\n");
}

void print(ll x, int suc = 1)
{
	printf("%" PRId64, x);
	if (suc == 1)
		printEoln();
	if (suc == 2)
		printSpace();
}

string readString()
{
	static char buf[3341000];
	scanf("%s", buf);
	return string(buf);
}

char *readCharArray()
{
	static char buf[3341000];
	static int bufUsed = 0;
	char *ret = buf + bufUsed;
	scanf("%s", ret);
	bufUsed += strlen(ret) + 1;
	return ret;
}

template <class T, class U>
void chmax(T &a, U b)
{
	if (a < b)
		a = b;
}

template <class T, class U>
void chmin(T &a, U b)
{
	if (b < a)
		a = b;
}

template <class T>
T Sq(const T &t)
{
	return t * t;
}

const ll infLL = LLONG_MAX / 3;

#ifdef int
const int inf = infLL;
#else
const int inf = INT_MAX / 2 - 100;
#endif

namespace Subtask4
{
ll Solve(vi x, vi h, vi l, vi r, vi y, int s, int g)
{
	int n = x.size();
	REP(k, 2)
	{
		int w = k == 0 ? s : g;
		vector<pi> p{pi(h[w], w)}, q{pi(h[w], w)};
		for (int i = w - 1; i >= 0; i--)
			if (h[i] > p.back().first)
				p.EB(h[i], i);
		for (int i = w + 1; i < n; i++)
			if (h[i] > q.back().first)
				q.EB(h[i], i);
		vi ll, rr, yy;
		REP(i, l.size())
		{
			if (l[i] < w && w < r[i])
			{
				int a, b;
				{
					auto itr = lower_bound(ALL(p), pi(y[i], -1));
					assert(itr != p.end());
					a = itr->second;
				}
				{
					auto itr = lower_bound(ALL(q), pi(y[i], -1));
					assert(itr != q.end());
					b = itr->second;
				}
				if (l[i] < a)
				{
					ll.PB(l[i]);
					rr.PB(a);
					yy.PB(y[i]);
				}
				if (a < b)
				{
					ll.PB(a);
					rr.PB(b);
					yy.PB(y[i]);
				}
				if (b < r[i])
				{
					ll.PB(b);
					rr.PB(r[i]);
					yy.PB(y[i]);
				}
			}
			else
			{
				ll.PB(l[i]);
				rr.PB(r[i]);
				yy.PB(y[i]);
			}
		}
		l = ll;
		r = rr;
		y = yy;
	}

	int m = l.size();

	vector<pi> posYX{pi(0, x[s]), pi(0, x[g])};
	{
		vector<tuple<int, int, int>> xty;
		REP(i, m)
		{
			xty.EB(x[l[i]], 0, y[i]);
			xty.EB(x[r[i]], 1, -y[i]);
		}

		sort(ALL(xty));
		multiset<int> ys;
		for (auto q : xty)
		{
			int j = get<0>(q), t = get<1>(q), i = get<2>(q) * (t == 0 ? 1 : -1);
			posYX.EB(i, j);
			auto itr = ys.lower_bound(i);
			if (itr != ys.begin())
			{
				--itr;
				posYX.EB(*itr, j);
			}
			if (t == 0)
				ys.insert(i);
			else
				ys.erase(ys.find(i));
		}

		sort(ALL(posYX));
		posYX.erase(unique(ALL(posYX)), posYX.end());
	}

	const auto Idx = [&](int i, int j) {
		return lower_bound(ALL(posYX), pi(i, j)) - posYX.begin();
	};

	int vs = posYX.size();
	vector<vector<pi>> graph(vs);
	const auto AddEdge = [&](int a, int b, int c) {
		graph[a].EB(b, c);
		graph[b].EB(a, c);
	};

	REP(i, m)
	{
		int k = Idx(y[i], x[l[i]]);
		while (k + 1 < int(posYX.size()) && posYX[k + 1] <= pi(y[i], x[r[i]]))
		{
			AddEdge(k, k + 1, posYX[k + 1].second - posYX[k].second);
			k++;
		}
	}

	vector<pi> posXY = posYX;
	for (auto &p : posXY)
		swap(p.first, p.second);
	sort(ALL(posXY));
	REP(i, vs - 1)
	{
		if (posXY[i].first == posXY[i + 1].first)
		{
			AddEdge(Idx(posXY[i].second, posXY[i].first), Idx(posXY[i + 1].second, posXY[i + 1].first), posXY[i + 1].second - posXY[i].second);
		}
	}

	vector<ll> dist(vs, infLL);
	using pli = tuple<ll, int>;
	//priority_queue<pli, vector<pli>, greater<pli>> pq;
	queue<pli> pq;
	const auto Reach = [&](int v, ll d) {
		if (dist[v] > d)
		{
			dist[v] = d;
			pq.push(pli(d, v));
		}
	};
	Reach(Idx(0, x[s]), 0);
	while (!pq.empty())
	{
		int v;
		ll d;
		//tie(d, v) = pq.top();
		tie(d,v)=pq.front();
		pq.pop();
		if (dist[v] != d)
			continue;
		for (auto e : graph[v])
			Reach(e.first, dist[v] + e.second);
	}

	return dist[Idx(0, x[g])] == infLL ? -1 : dist[Idx(0, x[g])];
}
} // namespace Subtask4

long long min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int S, int G)
{
	return Subtask4::Solve(X, H, L, R, Y, S, G);
}

Compilation message

walk.cpp: In function 'll read()':
walk.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%" SCNd64, &i);
  ~~~~~^~~~~~~~~~~~~~~~
walk.cpp: In function 'std::__cxx11::string readString()':
walk.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", buf);
  ~~~~~^~~~~~~~~~~
walk.cpp: In function 'char* readCharArray()':
walk.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", ret);
  ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Execution timed out 4030 ms 37564 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 9120 KB Output is correct
2 Correct 869 ms 44272 KB Output is correct
3 Correct 951 ms 45440 KB Output is correct
4 Correct 1287 ms 46392 KB Output is correct
5 Correct 1040 ms 49268 KB Output is correct
6 Correct 900 ms 45424 KB Output is correct
7 Correct 701 ms 24780 KB Output is correct
8 Correct 318 ms 22640 KB Output is correct
9 Correct 856 ms 42356 KB Output is correct
10 Correct 311 ms 25496 KB Output is correct
11 Correct 16 ms 1528 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 9120 KB Output is correct
2 Correct 869 ms 44272 KB Output is correct
3 Correct 951 ms 45440 KB Output is correct
4 Correct 1287 ms 46392 KB Output is correct
5 Correct 1040 ms 49268 KB Output is correct
6 Correct 900 ms 45424 KB Output is correct
7 Correct 701 ms 24780 KB Output is correct
8 Correct 318 ms 22640 KB Output is correct
9 Correct 856 ms 42356 KB Output is correct
10 Correct 311 ms 25496 KB Output is correct
11 Correct 16 ms 1528 KB Output is correct
12 Correct 831 ms 45032 KB Output is correct
13 Correct 678 ms 44792 KB Output is correct
14 Correct 947 ms 49272 KB Output is correct
15 Correct 707 ms 39288 KB Output is correct
16 Correct 924 ms 41060 KB Output is correct
17 Correct 1176 ms 46704 KB Output is correct
18 Correct 651 ms 39128 KB Output is correct
19 Correct 1082 ms 40924 KB Output is correct
20 Correct 439 ms 23536 KB Output is correct
21 Correct 41 ms 3064 KB Output is correct
22 Correct 499 ms 36108 KB Output is correct
23 Correct 442 ms 34908 KB Output is correct
24 Correct 352 ms 27304 KB Output is correct
25 Correct 477 ms 32156 KB Output is correct
26 Correct 291 ms 21928 KB Output is correct
27 Correct 1012 ms 49116 KB Output is correct
28 Correct 675 ms 44056 KB Output is correct
29 Correct 982 ms 45676 KB Output is correct
30 Correct 747 ms 25456 KB Output is correct
31 Correct 976 ms 42260 KB Output is correct
32 Execution timed out 4018 ms 24708 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Execution timed out 4030 ms 37564 KB Time limit exceeded
21 Halted 0 ms 0 KB -