oj.uz

Submission #599375

# Submission time Handle Problem Language Result Execution time Memory
599375 2022-07-19T13:13:07 Z FatihSolak Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 246744 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
int get(int a,int b,int c,int d){
	return abs(c-a) + abs(d-b);
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n = x.size();
	int m = l.size();
	map<int,vector<pair<int,int>>> adj[n];
	vector<int> st[n];
	vector<int> nd[n];
	for(int i = 0;i<m;i++){
		st[l[i]].push_back(y[i]);
		nd[r[i]].push_back(y[i]);
	}
	set<pair<int,int>> hh;
	for(int i = 0;i<n;i++){
		set<pair<int,int>> nw;
		while(hh.size() && hh.begin()->first <= h[i]){
			nw.insert({hh.begin()->first,i});
			adj[i][hh.begin()->first].push_back({hh.begin()->second,hh.begin()->first});
			adj[hh.begin()->second][hh.begin()->first].push_back({i,hh.begin()->first});
			hh.erase(hh.begin());
		}
		for(auto u:st[i]){
			hh.insert({u,i});
		}
		for(auto u:nw){
			hh.insert(u);
		}
		for(auto u:nd[i]){
			hh.erase(hh.lower_bound({u,0}));
		}
	}
	for(int i = 0;i<n;i++){
		vector<int> add = {0};
		for(auto u:adj[i]){
			add.push_back(u.first);
		}
		for(int j = 0;j<add.size()-1;j++){
			adj[i][add[j]].push_back({i,add[j+1]});
			adj[i][add[j+1]].push_back({i,add[j]});
		}
	}
	map<int,long long> dist[n];
	dist[s][0] = 0;
	priority_queue<pair<long long,pair<int,int>>> q;
	q.push({0,{s,0}});
	while(q.size()){
		auto tp = q.top();
		q.pop();
		tp.first *= -1;
		long long cost = tp.first;
		int a = tp.second.first;
		int b = tp.second.second;
		//cout << a << " " << b << " " << cost << endl;
		if(dist[a][b] != cost)
			continue;
		if(a == g && b == 0){
			return cost;
		}
		for(auto u:adj[a][b]){
			if(dist[u.first].count(u.second) == 0 || dist[u.first][u.second] > cost + get(x[a],b,x[u.first],u.second)){
				dist[u.first][u.second] = cost + get(x[a],b,x[u.first],u.second);
				q.push({-dist[u.first][u.second],u});
			}
		}
	}
	return -1;
}

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:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int j = 0;j<add.size()-1;j++){
      |                 ~^~~~~~~~~~~~~

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 Runtime error 1 ms 340 KB Execution killed with signal 6
4 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 1 ms 212 KB Output is correct
3 Correct 575 ms 114164 KB Output is correct
4 Correct 804 ms 188300 KB Output is correct
5 Correct 431 ms 123632 KB Output is correct
6 Correct 411 ms 111004 KB Output is correct
7 Correct 468 ms 124076 KB Output is correct
8 Correct 846 ms 153024 KB Output is correct
9 Correct 498 ms 126428 KB Output is correct
10 Correct 1203 ms 246744 KB Output is correct
11 Correct 321 ms 74968 KB Output is correct
12 Correct 243 ms 81700 KB Output is correct
13 Correct 940 ms 229320 KB Output is correct
14 Correct 210 ms 58532 KB Output is correct
15 Runtime error 150 ms 85284 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4033 ms 4180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4033 ms 4180 KB Time limit exceeded
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 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -