oj.uz

Submission #826062

# Submission time Handle Problem Language Result Execution time Memory
826062 2023-08-15T10:09:31 Z tolbi Sky Walking (IOI19_walk) C++17
0 / 100
 2360 ms 1048576 KB 
#pragma optimize("Bismilahirrahmanirrahim")
//█▀█─█──█──█▀█─█▀█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define vint(x) vector<int> x
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "walk.h"

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 = y.size();
	vector<int> lelx(n);
	iota(lelx.begin(), lelx.end(), 0);
	vector<int> lely(m,-1);
	vector<array<int,4>> isl;
	for (int i = 0; i < m; i++){
		isl.push_back({l[i],y[i],i,1});
		isl.push_back({r[i]+1,y[i],i,-1});
	}
	sortarr(isl);
	int indi = 0;
	set<pair<int,int>> st;
	vector<vector<pair<int,int>>> arr(n);
	vector<int> xpos(n);
	for (int i = 0; i < n; ++i)
	{
		xpos[i]=x[i];
	}
	vector<int> ypos(n,0);
	for (int i = 0; i < n; i++){
		while (indi<isl.size() && isl[indi][0]<=i){
			if (isl[indi][3]==1){
				st.insert({isl[indi][1],isl[indi][2]});
			}
			else {
				st.erase({isl[indi][1],isl[indi][2]});
			}
			indi++;
		}
		auto it = st.begin();
		while (it!=st.end()){
			if (it->first>h[i]) break;
			int node = arr.size();
			xpos.push_back(x[i]);
			ypos.push_back(it->first);
			arr.push_back(vector<pair<int,int>>());
			if (lely[it->second]!=-1){
				arr[lely[it->second]].push_back({node,xpos[node]-xpos[lely[it->second]]});
				arr[node].push_back({lely[it->second],xpos[node]-xpos[lely[it->second]]});
			}
			arr[lelx[i]].push_back({node,ypos[node]-ypos[lelx[i]]});
			arr[node].push_back({lelx[i],ypos[node]-ypos[lelx[i]]});
			lelx[i]=node;
			lely[it->second]=node;
			it++;
		}
	}
	vector<int> dp(arr.size(), -1);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({0,s});
	while (pq.size()){
		int node = pq.top().second;
		int w = pq.top().first;
		pq.pop();
		if (dp[node]!=-1) continue;
		dp[node]=w;
		for (int i = 0; i < arr[node].size(); i++){
			if (dp[arr[node][i].first]!=-1) continue;
			pq.push({w+arr[node][i].second,arr[node][i].first});
		}
	}
	return dp[g];
}

Compilation message

walk.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismilahirrahmanirrahim")
      | 
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:46:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   while (indi<isl.size() && isl[indi][0]<=i){
      |          ~~~~^~~~~~~~~~~
walk.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 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 Incorrect 1 ms 212 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 13516 KB Output is correct
2 Correct 2355 ms 457064 KB Output is correct
3 Runtime error 2360 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 49 ms 13516 KB Output is correct
2 Correct 2355 ms 457064 KB Output is correct
3 Runtime error 2360 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 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 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 Incorrect 1 ms 212 KB Output isn't correct
17 Halted 0 ms 0 KB -