oj.uz

Submission #1046047

# Submission time Handle Problem Language Result Execution time Memory
1046047 2024-08-06T09:25:05 Z idas Sky Walking (IOI19_walk) C++17
10 / 100
 340 ms 410688 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<pii, vector<pii>, greater<pii>> 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 15 ms 115292 KB Output is correct
2 Correct 15 ms 115216 KB Output is correct
3 Correct 16 ms 115288 KB Output is correct
4 Correct 14 ms 115292 KB Output is correct
5 Correct 15 ms 115384 KB Output is correct
6 Correct 15 ms 115292 KB Output is correct
7 Correct 15 ms 115384 KB Output is correct
8 Correct 16 ms 115292 KB Output is correct
9 Correct 15 ms 115292 KB Output is correct
10 Correct 15 ms 115288 KB Output is correct
11 Correct 15 ms 115220 KB Output is correct
12 Correct 14 ms 115292 KB Output is correct
13 Correct 15 ms 115236 KB Output is correct
14 Correct 16 ms 115292 KB Output is correct
15 Correct 16 ms 115292 KB Output is correct
16 Correct 16 ms 115180 KB Output is correct
17 Correct 15 ms 115292 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 115292 KB Output is correct
2 Correct 15 ms 115288 KB Output is correct
3 Correct 266 ms 154248 KB Output is correct
4 Incorrect 340 ms 166520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 122568 KB Output is correct
2 Runtime error 260 ms 410688 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 55 ms 122568 KB Output is correct
2 Runtime error 260 ms 410688 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 15 ms 115292 KB Output is correct
2 Correct 15 ms 115216 KB Output is correct
3 Correct 16 ms 115288 KB Output is correct
4 Correct 14 ms 115292 KB Output is correct
5 Correct 15 ms 115384 KB Output is correct
6 Correct 15 ms 115292 KB Output is correct
7 Correct 15 ms 115384 KB Output is correct
8 Correct 16 ms 115292 KB Output is correct
9 Correct 15 ms 115292 KB Output is correct
10 Correct 15 ms 115288 KB Output is correct
11 Correct 15 ms 115220 KB Output is correct
12 Correct 14 ms 115292 KB Output is correct
13 Correct 15 ms 115236 KB Output is correct
14 Correct 16 ms 115292 KB Output is correct
15 Correct 16 ms 115292 KB Output is correct
16 Correct 16 ms 115180 KB Output is correct
17 Correct 15 ms 115292 KB Output is correct
18 Correct 15 ms 115292 KB Output is correct
19 Correct 15 ms 115288 KB Output is correct
20 Correct 266 ms 154248 KB Output is correct
21 Incorrect 340 ms 166520 KB Output isn't correct
22 Halted 0 ms 0 KB -