oj.uz

Submission #1046050

# Submission time Handle Problem Language Result Execution time Memory
1046050 2024-08-06T09:26:00 Z idas Sky Walking (IOI19_walk) C++17
24 / 100
 414 ms 410828 KB 
#include "walk.h"
#include "bits/stdc++.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)((x).size()))
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N=1e5+10, M=20*N;
int n, m, id, hgt[M], gr[M];
ll dist[M];
vector<pii> ins[M];
vector<pii> ad[M];
bool v[M];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int str, int g) {
	n=sz(x); m=sz(l);

	vector<pii> buildings;
	FOR(i, 0, n) {
		buildings.pb({h[i],i});
	}
	sort(buildings.begin(), buildings.end());
	reverse(buildings.begin(), buildings.end());

	set<pii> xs;
	FOR(i, 0, n) xs.insert({x[i],i});

	vector<pii> walks;
	FOR(i, 0, m) {
		walks.pb({y[i],i});
	}
	sort(walks.begin(), walks.end());

	id=n;
	for(auto[y, i] : walks) {
		while(!buildings.empty() && buildings.back().f<y) {
			int in=buildings.back().s;
			xs.erase({x[in],in});
			buildings.pop_back();
		}

		auto it=xs.lower_bound({x[l[i]],0});
		while(it==xs.end()) {}
		// assert((it->f)==x[l[i]]);

		int prv=-1, pos=0;
		while(true) {
			if(prv!=-1) {
				int w=(it->f)-pos;
				ad[prv].pb({id,w});
				ad[id].pb({prv,w});
			}

			prv=id; pos=it->f; hgt[id]=y; gr[id]=it->s;
			ins[it->s].pb({y,id++});

			if(it->s==r[i]) break;
			++it;
		}
	}

	FOR(i, 0, n) {
		hgt[i]=0; gr[i]=i;
		ins[i].pb({0,i});
		sort(ins[i].begin(), ins[i].end());
	}

	FOR(i, 0, 20*N) dist[i]=-1;

	priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
	dist[str]=0; q.push({dist[str],str});
	while(!q.empty()) {
		int id=q.top().s; q.pop();

		if(!v[id]) v[id]=true;
		else continue;

		int i=lower_bound(ins[gr[id]].begin(), ins[gr[id]].end(), pii{hgt[id],id})-ins[gr[id]].begin();

		if(i+1<ins[gr[id]].size()) {
			int upper=ins[gr[id]][i+1].s, add=hgt[upper]-hgt[id];
			if(dist[upper]==-1 || dist[upper]>dist[id]+add) {
				dist[upper]=dist[id]+add;
				q.push({dist[upper],upper});
			}
		}
		if(i-1>=0) {
			int lower=ins[gr[id]][i-1].s, add=hgt[id]-hgt[lower];

			if(dist[lower]==-1 || dist[lower]>dist[id]+add) {
				dist[lower]=dist[id]+add;
				q.push({dist[lower],lower});
			}
		}

		for(auto [idx, w] : ad[id]) {
			if(dist[idx]==-1 || dist[idx]>dist[id]+w) {
				dist[idx]=dist[id]+w;
				q.push({dist[idx],idx});
			}
		}
	}

	return dist[g];
}
/*
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
0 6

3 5
0 3
3 3
5 2
0 1 2
0 1 1
1 2 1
1 2 2
0 1 3
2 0
*/

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:87:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   if(i+1<ins[gr[id]].size()) {
      |      ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 115292 KB Output is correct
2 Correct 15 ms 115292 KB Output is correct
3 Correct 15 ms 115256 KB Output is correct
4 Correct 15 ms 115292 KB Output is correct
5 Correct 15 ms 115324 KB Output is correct
6 Correct 15 ms 115292 KB Output is correct
7 Correct 15 ms 115292 KB Output is correct
8 Correct 15 ms 115292 KB Output is correct
9 Correct 15 ms 115292 KB Output is correct
10 Correct 15 ms 115292 KB Output is correct
11 Correct 15 ms 115288 KB Output is correct
12 Correct 15 ms 115288 KB Output is correct
13 Correct 15 ms 115292 KB Output is correct
14 Correct 15 ms 115288 KB Output is correct
15 Correct 16 ms 115176 KB Output is correct
16 Correct 15 ms 115340 KB Output is correct
17 Correct 15 ms 115288 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 115292 KB Output is correct
2 Correct 17 ms 115228 KB Output is correct
3 Correct 267 ms 154316 KB Output is correct
4 Correct 334 ms 162372 KB Output is correct
5 Correct 173 ms 156996 KB Output is correct
6 Correct 155 ms 153092 KB Output is correct
7 Correct 156 ms 156740 KB Output is correct
8 Correct 352 ms 166600 KB Output is correct
9 Correct 205 ms 157340 KB Output is correct
10 Correct 414 ms 180800 KB Output is correct
11 Correct 183 ms 141640 KB Output is correct
12 Correct 166 ms 138988 KB Output is correct
13 Correct 389 ms 175024 KB Output is correct
14 Correct 118 ms 136004 KB Output is correct
15 Correct 127 ms 137796 KB Output is correct
16 Correct 133 ms 136776 KB Output is correct
17 Correct 129 ms 136008 KB Output is correct
18 Correct 101 ms 136584 KB Output is correct
19 Correct 18 ms 116316 KB Output is correct
20 Correct 50 ms 126616 KB Output is correct
21 Correct 115 ms 136232 KB Output is correct
22 Correct 138 ms 138052 KB Output is correct
23 Correct 138 ms 141928 KB Output is correct
24 Correct 137 ms 137916 KB Output is correct
25 Correct 132 ms 137032 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 122828 KB Output is correct
2 Runtime error 256 ms 410828 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 56 ms 122828 KB Output is correct
2 Runtime error 256 ms 410828 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 17 ms 115292 KB Output is correct
2 Correct 15 ms 115292 KB Output is correct
3 Correct 15 ms 115256 KB Output is correct
4 Correct 15 ms 115292 KB Output is correct
5 Correct 15 ms 115324 KB Output is correct
6 Correct 15 ms 115292 KB Output is correct
7 Correct 15 ms 115292 KB Output is correct
8 Correct 15 ms 115292 KB Output is correct
9 Correct 15 ms 115292 KB Output is correct
10 Correct 15 ms 115292 KB Output is correct
11 Correct 15 ms 115288 KB Output is correct
12 Correct 15 ms 115288 KB Output is correct
13 Correct 15 ms 115292 KB Output is correct
14 Correct 15 ms 115288 KB Output is correct
15 Correct 16 ms 115176 KB Output is correct
16 Correct 15 ms 115340 KB Output is correct
17 Correct 15 ms 115288 KB Output is correct
18 Correct 15 ms 115292 KB Output is correct
19 Correct 17 ms 115228 KB Output is correct
20 Correct 267 ms 154316 KB Output is correct
21 Correct 334 ms 162372 KB Output is correct
22 Correct 173 ms 156996 KB Output is correct
23 Correct 155 ms 153092 KB Output is correct
24 Correct 156 ms 156740 KB Output is correct
25 Correct 352 ms 166600 KB Output is correct
26 Correct 205 ms 157340 KB Output is correct
27 Correct 414 ms 180800 KB Output is correct
28 Correct 183 ms 141640 KB Output is correct
29 Correct 166 ms 138988 KB Output is correct
30 Correct 389 ms 175024 KB Output is correct
31 Correct 118 ms 136004 KB Output is correct
32 Correct 127 ms 137796 KB Output is correct
33 Correct 133 ms 136776 KB Output is correct
34 Correct 129 ms 136008 KB Output is correct
35 Correct 101 ms 136584 KB Output is correct
36 Correct 18 ms 116316 KB Output is correct
37 Correct 50 ms 126616 KB Output is correct
38 Correct 115 ms 136232 KB Output is correct
39 Correct 138 ms 138052 KB Output is correct
40 Correct 138 ms 141928 KB Output is correct
41 Correct 137 ms 137916 KB Output is correct
42 Correct 132 ms 137032 KB Output is correct
43 Correct 56 ms 122828 KB Output is correct
44 Runtime error 256 ms 410828 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -