oj.uz

Submission #411405

# Submission time Handle Problem Language Result Execution time Memory
411405 2021-05-25T08:27:05 Z 장태환(#7572) Sky Walking (IOI19_walk) C++17
0 / 100
 635 ms 297844 KB 
#include "walk.h"
#include <algorithm>
#include <set>
#include <queue>
#include <string.h>
using namespace std;
vector<pair<int, int>>re;
vector<pair<int, int>>link[2000100];
pair<int, int>bef[200100];
multiset<pair<int,int>>se;
long long dist[2000100];
int vis[2000100];
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)
{
	int N = x.size();
	int M = l.size();
	int i;
	int vc = 0;
	for (i = 0; i < N; i++)
	{
		re.push_back({ x[i],i });
	}
	for (i = 0; i < M; i++)
	{
		re.push_back({ x[l[i]],-i-1 });
		re.push_back({ x[r[i]] + 1,-i-M-1 });
	}
	sort(re.begin(), re.end());

	int curv = N;
	for (i = 0; i < re.size(); i++)
	{
		if (re[i].second >= 0)
		{
			int befh = 0;
			int befv = re[i].second;
			for (auto j = se.begin(); j != se.end(); j++)
			{
				if ((*j).first > h[re[i].second])
					break;
				int he = (*j).first;
				link[befv].push_back({ curv,he - befh });
				link[curv].push_back({ befv,he - befh });
				int ve = (*j).second;
				if (bef[ve].second)
				{
					link[bef[ve].second].push_back({ curv,re[i].first - bef[ve].first });
					link[curv].push_back({ bef[ve].second,re[i].first - bef[ve].first });
				}
				bef[ve] = { re[i].first,curv };
				befh = he;
				befv = curv;
				curv++;
			}
		}
		else if (re[i].second >=-M)
		{
			int te = -re[i].second - 1;
			se.insert({ y[te],te });
		}
		else
		{
			int te = -re[i].second - 1-M;
			se.erase({ y[te],te });
		}
	}
	memset(dist, 1, sizeof(dist));
	priority_queue<pair<int, int>>pq;
	pq.push({ 0,s });
	while (pq.size())
	{
		auto a = pq.top();
		pq.pop();
		if (vis[a.second])
			continue;
		vis[a.second] = 1;
		for (i = 0; i < link[a.second].size(); i++)
		{
			if (dist[link[a.second][i].first] > -a.first + link[a.second][i].second)
			{
				dist[link[a.second][i].first] = -a.first + link[a.second][i].second;
				pq.push({ -dist[link[a.second][i].first],link[a.second][i].first });
			}
		}
	}
	return (dist[g]>(1LL<<50))?-1:dist[g];
}

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:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (i = 0; i < re.size(); i++)
      |              ~~^~~~~~~~~~~
walk.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (i = 0; i < link[a.second].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~
walk.cpp:18:6: warning: unused variable 'vc' [-Wunused-variable]
   18 |  int vc = 0;
      |      ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62832 KB Output is correct
2 Correct 36 ms 62956 KB Output is correct
3 Correct 31 ms 62884 KB Output is correct
4 Correct 32 ms 62880 KB Output is correct
5 Correct 32 ms 62912 KB Output is correct
6 Correct 32 ms 62856 KB Output is correct
7 Correct 31 ms 62896 KB Output is correct
8 Correct 32 ms 62960 KB Output is correct
9 Correct 32 ms 62788 KB Output is correct
10 Correct 32 ms 62860 KB Output is correct
11 Correct 35 ms 62876 KB Output is correct
12 Correct 34 ms 62916 KB Output is correct
13 Correct 31 ms 62868 KB Output is correct
14 Correct 33 ms 62848 KB Output is correct
15 Correct 32 ms 62868 KB Output is correct
16 Incorrect 33 ms 62880 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62796 KB Output is correct
2 Correct 35 ms 62884 KB Output is correct
3 Correct 441 ms 105844 KB Output is correct
4 Incorrect 420 ms 112456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 71816 KB Output is correct
2 Runtime error 635 ms 297844 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 71816 KB Output is correct
2 Runtime error 635 ms 297844 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62832 KB Output is correct
2 Correct 36 ms 62956 KB Output is correct
3 Correct 31 ms 62884 KB Output is correct
4 Correct 32 ms 62880 KB Output is correct
5 Correct 32 ms 62912 KB Output is correct
6 Correct 32 ms 62856 KB Output is correct
7 Correct 31 ms 62896 KB Output is correct
8 Correct 32 ms 62960 KB Output is correct
9 Correct 32 ms 62788 KB Output is correct
10 Correct 32 ms 62860 KB Output is correct
11 Correct 35 ms 62876 KB Output is correct
12 Correct 34 ms 62916 KB Output is correct
13 Correct 31 ms 62868 KB Output is correct
14 Correct 33 ms 62848 KB Output is correct
15 Correct 32 ms 62868 KB Output is correct
16 Incorrect 33 ms 62880 KB Output isn't correct
17 Halted 0 ms 0 KB -