oj.uz

Submission #598593

# Submission time Handle Problem Language Result Execution time Memory
598593 2022-07-18T14:39:56 Z yutabi Sky Walking (IOI19_walk) C++14
24 / 100
 2548 ms 1048576 KB 
#include "walk.h"


#include <bits/stdc++.h>
using namespace std;


#define INF 1000000000000000007
#define pb push_back


typedef long long ll;
typedef pair <ll,ll> ii;





vector <vector <ii> > graph;

vector <ll> res;
priority_queue <ii> pq;
vector <bool> v;


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)
{
	ll n=x.size();
	ll m=l.size();

	vector <ii> last_added(n,ii(-1,-1));

	ll k=0;

	vector <ii> build;
	vector <pair <ll,ii> > sky;

	for(ll i=0;i<n;i++)
	{
		build.pb(ii(h[i],i));
	}

	for(ll i=0;i<m;i++)
	{
		sky.pb(make_pair(y[i],ii(l[i],r[i])));
	}

	sort(build.begin(),build.end());
	sort(sky.rbegin(),sky.rend());

	set <ll> builds;

	for(ll i=0;i<m;i++)
	{
		while(build.size() && build.back().first>=sky[i].first)
		{
			builds.insert(build.back().second);

			build.pop_back();
		}

		auto it=builds.lower_bound(sky[i].second.first);

		ll last=*it;

		ll height=sky[i].first;

		graph.pb({});
		res.pb(-1);
		v.pb(0);

		if(last_added[last].first!=-1)
		{
			graph[last_added[last].first].pb(ii(k,last_added[last].second-height));
			graph[k].pb(ii(last_added[last].first,last_added[last].second-height));
		}

		last_added[last]=ii(k,height);

		k++;






		it++;

		while(it!=builds.end() && *it<=sky[i].second.second)
		{
			ll curr=*it;

			graph.pb({});
			res.pb(-1);
			v.pb(0);

			graph[k-1].pb(ii(k,x[curr]-x[last]));
			graph[k].pb(ii(k-1,x[curr]-x[last]));

			if(last_added[curr].first!=-1)
			{
				graph[last_added[curr].first].pb(ii(k,last_added[curr].second-height));
				graph[k].pb(ii(last_added[curr].first,last_added[curr].second-height));
			}

			last_added[curr]=ii(k,height);

			k++;

			last=curr;

			it++;
		}
	}

	ll start_index;
	ll end_index;

	for(ll i=0;i<n;i++)
	{
		graph.pb({});
		res.pb(-1);
		v.pb(0);

		if(last_added[i].first!=-1)
		{
			graph[last_added[i].first].pb(ii(k,last_added[i].second-0));
			graph[k].pb(ii(last_added[i].first,last_added[i].second-0));
		}

		if(s==i)
		{
			start_index=k;
		}

		if(g==i)
		{
			end_index=k;
		}

		k++;
	}

	pq.push(ii(0,start_index));

	while(pq.size())
	{
		int index=pq.top().second;
		ll dist=-pq.top().first;

		pq.pop();

		if(v[index])
		{
			continue;
		}

		res[index]=dist;

		v[index]=1;

		for(int i=0;i<graph[index].size();i++)
		{
			if(v[graph[index][i].first]==0)
			{
				pq.push(ii(-(dist+graph[index][i].second),graph[index][i].first));
			}
		}
	}

	
	return res[end_index];
}

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:162:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |   for(int i=0;i<graph[index].size();i++)
      |               ~^~~~~~~~~~~~~~~~~~~~
walk.cpp:172:22: warning: 'end_index' may be used uninitialized in this function [-Wmaybe-uninitialized]
  172 |  return res[end_index];
      |                      ^

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 471 ms 85404 KB Output is correct
4 Correct 582 ms 100580 KB Output is correct
5 Correct 346 ms 88172 KB Output is correct
6 Correct 314 ms 84360 KB Output is correct
7 Correct 342 ms 88288 KB Output is correct
8 Correct 572 ms 107648 KB Output is correct
9 Correct 422 ms 86460 KB Output is correct
10 Correct 741 ms 154756 KB Output is correct
11 Correct 336 ms 52096 KB Output is correct
12 Correct 280 ms 47372 KB Output is correct
13 Correct 691 ms 119040 KB Output is correct
14 Correct 183 ms 46456 KB Output is correct
15 Correct 170 ms 47100 KB Output is correct
16 Correct 158 ms 45800 KB Output is correct
17 Correct 154 ms 45084 KB Output is correct
18 Correct 123 ms 42280 KB Output is correct
19 Correct 6 ms 2388 KB Output is correct
20 Correct 71 ms 23484 KB Output is correct
21 Correct 137 ms 45848 KB Output is correct
22 Correct 154 ms 46276 KB Output is correct
23 Correct 194 ms 51828 KB Output is correct
24 Correct 155 ms 46112 KB Output is correct
25 Correct 155 ms 45452 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16664 KB Output is correct
2 Correct 2548 ms 568040 KB Output is correct
3 Runtime error 1547 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16664 KB Output is correct
2 Correct 2548 ms 568040 KB Output is correct
3 Runtime error 1547 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 471 ms 85404 KB Output is correct
21 Correct 582 ms 100580 KB Output is correct
22 Correct 346 ms 88172 KB Output is correct
23 Correct 314 ms 84360 KB Output is correct
24 Correct 342 ms 88288 KB Output is correct
25 Correct 572 ms 107648 KB Output is correct
26 Correct 422 ms 86460 KB Output is correct
27 Correct 741 ms 154756 KB Output is correct
28 Correct 336 ms 52096 KB Output is correct
29 Correct 280 ms 47372 KB Output is correct
30 Correct 691 ms 119040 KB Output is correct
31 Correct 183 ms 46456 KB Output is correct
32 Correct 170 ms 47100 KB Output is correct
33 Correct 158 ms 45800 KB Output is correct
34 Correct 154 ms 45084 KB Output is correct
35 Correct 123 ms 42280 KB Output is correct
36 Correct 6 ms 2388 KB Output is correct
37 Correct 71 ms 23484 KB Output is correct
38 Correct 137 ms 45848 KB Output is correct
39 Correct 154 ms 46276 KB Output is correct
40 Correct 194 ms 51828 KB Output is correct
41 Correct 155 ms 46112 KB Output is correct
42 Correct 155 ms 45452 KB Output is correct
43 Correct 52 ms 16664 KB Output is correct
44 Correct 2548 ms 568040 KB Output is correct
45 Runtime error 1547 ms 1048576 KB Execution killed with signal 9
46 Halted 0 ms 0 KB -