oj.uz

Submission #723939

# Submission time Handle Problem Language Result Execution time Memory
723939 2023-04-14T13:34:01 Z LittleCube Sky Walking (IOI19_walk) C++14
14 / 100
 2001 ms 641540 KB 
#pragma GCC optimize("Ofast")
#include "walk.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

ll N, M, K, S, T, dis[5000000];
vector<pii> E[5000000], ver[100005], hor[100005], table[100005][20];

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
	N = x.size(), M = l.size();
	for (int i = 0; i < N; i++)
		table[i][0].emplace_back(pll(h[i], i));
	for (int p = 0; p + 1 < 18; p++)
		for (int i = 0; i + (1 << p) < N; i++)
		{
			for (auto j : table[i][p])
				table[i][p + 1].emplace_back(j);
			for (auto j : table[i + (1 << p)][p])
				table[i][p + 1].emplace_back(j);
			sort(table[i][p + 1].begin(), table[i][p + 1].end(), greater<pll>());
			if (table[i][p + 1].size() > 10)
				table[i][p + 1].resize(10);
		}
	for (int i = 0; i < N; i++)
	{
		++K;
		ver[i].emplace_back(pll(0, K));
		if (i == s)
			S = K;
		if (i == g)
			T = K;
	}
	for (int i = 0; i < M; i++)
	{
		int lg = __lg(r[i] - l[i] + 1);
		vector<pll> mango;
		for (auto j : table[l[i]][lg])
			mango.emplace_back(j);
		for (auto j : table[r[i] - (1 << lg) + 1][lg])
			mango.emplace_back(j);

		for (auto [_, j] : mango)
		{
			if (y[i] <= h[j])
			{
				++K;
				ver[j].emplace_back(pll(y[i], K));
				hor[i].emplace_back(pll(x[j], K));
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		sort(ver[i].begin(), ver[i].end());
		for (int j = 0; j + 1 < ver[i].size(); j++)
			E[ver[i][j].S].emplace_back(ver[i][j + 1].S, ver[i][j + 1].F - ver[i][j].F),
			E[ver[i][j + 1].S].emplace_back(ver[i][j].S, ver[i][j + 1].F - ver[i][j].F);
	}
	for (int i = 0; i < M; i++)
	{
		sort(hor[i].begin(), hor[i].end());
		for (int j = 0; j + 1 < hor[i].size(); j++)
			E[hor[i][j].S].emplace_back(hor[i][j + 1].S, hor[i][j + 1].F - hor[i][j].F),
				E[hor[i][j + 1].S].emplace_back(hor[i][j].S, hor[i][j + 1].F - hor[i][j].F);
	}
	for (int i = 0; i <= K; i++)
		dis[i] = 2e18;
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	dis[S] = 0;
	pq.push(pll(0, S));
	while (!pq.empty())
	{
		auto [d, u] = pq.top();
		pq.pop();
		if (d > dis[u])
			continue;
		for (auto [v, w] : E[u])
			if (dis[u] + w < dis[v])
			{
				dis[v] = dis[u] + w;
				pq.push(pll(dis[v], v));
			}
	}
	assert(K < 5000000);
	return (dis[T] >= 1e18 ? -1 : dis[T]);
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:48:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |   for (auto [_, j] : mango)
      |             ^
walk.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (int j = 0; j + 1 < ver[i].size(); j++)
      |                   ~~~~~~^~~~~~~~~~~~~~~
walk.cpp:68:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int j = 0; j + 1 < hor[i].size(); j++)
      |                   ~~~~~~^~~~~~~~~~~~~~~
walk.cpp:79:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |   auto [d, u] = pq.top();
      |        ^
walk.cpp:83:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |   for (auto [v, w] : E[u])
      |             ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 169316 KB Output is correct
2 Correct 93 ms 169328 KB Output is correct
3 Correct 93 ms 169316 KB Output is correct
4 Correct 97 ms 169328 KB Output is correct
5 Correct 91 ms 169464 KB Output is correct
6 Correct 91 ms 169560 KB Output is correct
7 Incorrect 103 ms 169476 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 169264 KB Output is correct
2 Correct 103 ms 169304 KB Output is correct
3 Correct 962 ms 289724 KB Output is correct
4 Correct 1728 ms 606348 KB Output is correct
5 Correct 1494 ms 593372 KB Output is correct
6 Correct 1373 ms 584176 KB Output is correct
7 Correct 1424 ms 596856 KB Output is correct
8 Correct 1178 ms 315924 KB Output is correct
9 Correct 1328 ms 520984 KB Output is correct
10 Correct 1979 ms 641540 KB Output is correct
11 Correct 811 ms 345172 KB Output is correct
12 Correct 1213 ms 555028 KB Output is correct
13 Correct 2001 ms 635432 KB Output is correct
14 Correct 1070 ms 540704 KB Output is correct
15 Correct 1091 ms 541732 KB Output is correct
16 Correct 1109 ms 509336 KB Output is correct
17 Correct 1036 ms 501428 KB Output is correct
18 Correct 1119 ms 535112 KB Output is correct
19 Correct 142 ms 181392 KB Output is correct
20 Correct 462 ms 332484 KB Output is correct
21 Correct 1035 ms 454156 KB Output is correct
22 Correct 1194 ms 554156 KB Output is correct
23 Correct 1122 ms 545020 KB Output is correct
24 Correct 1162 ms 522980 KB Output is correct
25 Correct 1074 ms 499056 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 213660 KB Output is correct
2 Incorrect 1579 ms 336184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 213660 KB Output is correct
2 Incorrect 1579 ms 336184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 169316 KB Output is correct
2 Correct 93 ms 169328 KB Output is correct
3 Correct 93 ms 169316 KB Output is correct
4 Correct 97 ms 169328 KB Output is correct
5 Correct 91 ms 169464 KB Output is correct
6 Correct 91 ms 169560 KB Output is correct
7 Incorrect 103 ms 169476 KB Output isn't correct
8 Halted 0 ms 0 KB -