oj.uz

Submission #775521

# Submission time Handle Problem Language Result Execution time Memory
775521 2023-07-06T13:17:24 Z Abrar_Al_Samit Sky Walking (IOI19_walk) C++17
0 / 100
 2856 ms 100880 KB 
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;


const int nax = 1e6 + 3;
const long long INF = 1e18;

int n, m;
long long 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();

	map<int, vector<int>>row, col;

	map<int, vector<int>>ens;
	for(int i=0; i<m; ++i) {
		ens[l[i]].push_back(y[i]);
		ens[r[i]].push_back(-y[i]);
	}


	multiset<int>ms;
	for(int i=0; i<n; ++i) {
		for(int j : ens[i]) {
			if(j>0) {
				ms.insert(j);
			}
		}

		for(int j : ms) {
			if(j<=h[i]) {
				row[j].push_back(x[i]);
				col[x[i]].push_back(j);
			} else break;
		}

		for(int j : ens[i]) {
			if(j<0) {
				ms.erase(ms.find(-j));
			}
		}
	}

	row[0].push_back(x[s]);
	col[x[s]].push_back(0);
	row[0].push_back(x[g]);
	col[x[g]].push_back(0);

	map<int, vector<int>>can;
	for(auto &it : row) {
		sort(it.second.begin(), it.second.end());

		can[it.first].resize(it.second.size());
	}
	for(auto &it : col) {
		sort(it.second.begin(), it.second.end());
	}

	for(int i=0; i<m; ++i) {
		int j = lower_bound(row[y[i]].begin(), row[y[i]].end(), x[l[i]]) -
			row[y[i]].begin();

		while(row[y[i]][j]!=x[r[i]]) {
			can[y[i]][j] = 1;
			++j;
		}
	}


	map<pair<int,int>,long long>dist;
	for(auto it : row) {
		for(int j : it.second) {
			dist[{j, it.first}] = INF;
		}
	}

	dist[{x[s], 0}] = 0;
	priority_queue<tuple<long long, int,int>>pq;
	pq.emplace(0, x[s], 0);

	while(!pq.empty()) {
		auto [w, x, y] = pq.top();
		pq.pop();
		w = -w;

		if(w!=dist[{x, y}]) continue;

		int j = lower_bound(row[y].begin(), row[y].end(), x) - row[y].begin();
		if(j>0 && can[y][j-1]) {
			int px = row[y][j-1];
			if(dist[{px, y}]>w+x-px) {
				dist[{px, y}] = w + x-px;
				pq.emplace(-dist[{px, y}], px, y);
			}
		}
		if(j+1<row[y].size() && can[y][j]) {
			int nx = row[y][j+1];
			if(dist[{nx, y}]>w+nx-x) {
				dist[{nx, y}] = w + nx-x;
				pq.emplace(-dist[{nx, y}], nx, y);
			}
		}

		j = lower_bound(col[x].begin(), col[x].end(), y) - col[x].begin();

		if(j>0) {
			int py = col[x][j-1];
			if(dist[{x, py}]>w+y-py) {
				dist[{x, py}] = w + y-py;
				pq.emplace(-dist[{x, py}], x, py);
			}
		}
		if(j+1<col[x].size()) {
			int ny = col[x][j+1];
			if(dist[{x, ny}]>w+ny-y) {
				dist[{x, ny}] = w + ny-y;
				pq.emplace(-dist[{x, ny}], x, ny);
			}
		}
	}
	return dist[{x[g], 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:98:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   if(j+1<row[y].size() && can[y][j]) {
      |      ~~~^~~~~~~~~~~~~~
walk.cpp:115:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   if(j+1<col[x].size()) {
      |      ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Incorrect 1 ms 304 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2856 ms 81072 KB Output is correct
4 Correct 2056 ms 100880 KB Output is correct
5 Correct 680 ms 86964 KB Output is correct
6 Correct 666 ms 81836 KB Output is correct
7 Incorrect 644 ms 87204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 10216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 10216 KB Output isn't correct
2 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 1 ms 212 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Incorrect 1 ms 304 KB Output isn't correct
5 Halted 0 ms 0 KB -