oj.uz

Submission #433883

# Submission time Handle Problem Language Result Execution time Memory
433883 2021-06-20T11:49:21 Z kostia244 Sky Walking (IOI19_walk) C++17
0 / 100
 581 ms 114752 KB 
#include "walk.h"
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int U, int V) {
	int n = x.size(), m = l.size();
	vector<vector<array<int, 2>>> g;
	vector<vector<int>> on(n+1);
	vector<int> col, lst(m, -1), start(n);
	for(int i = 0; i < m; i++) {
		on[l[i]].push_back(i);
		on[r[i]+1].push_back(-1-i);
	}
	set<array<int, 2>> hv;
	for(int i = 0; i < n; i++) {
		for(auto id : on[i]) {
			if(id < 0) {
				id = -id-1;
				hv.erase({y[id], id});
			} else
				hv.insert({y[id], id});
		}
		start[i] = g.size();
		g.push_back({});//(i, 0)
		col.push_back(i);
		int loh = 0;
		auto it = hv.begin();
		while(it != hv.end() && it->at(0) <= h[i]) {
			int id = it->at(1);
			g.back().push_back({g.size(), y[id]-loh});
			g.push_back({{g.size()-1, y[id]-loh}});
			//cout << g.size()-1 << " " << g.size()-2 << " " << y[id]-loh << endl;
			col.push_back(i);
			//cout << i << " " << id << "uwu\n";
			if(lst[id] != -1) {
				g[lst[id]].push_back({g.size()-1, x[i]-x[col[lst[id]]]});
				g.back().push_back({lst[id], x[i]-x[col[lst[id]]]});
			}
			lst[id] = g.size()-1;
			loh = y[id];
			it++;
		}	
	}
	U = start[U];
	V = start[V];
	priority_queue<array<ll, 2>> pq;
	vector<ll> dist(g.size(), 1ll<<60);
	auto enq = [&](int v, ll d) {
		//if(col[v] > 1) return;///REMOVE
		if(dist[v] <= d) return;
		dist[v] = d;
		pq.push({-dist[v], v});
	};
	//cout << U << " " << V << endl;
	for(enq(U, 0); !pq.empty(); pq.pop()) {
		auto [di, v] = pq.top();
		di *= -1;
		if(di > dist[v]) continue;
		//cout << v << " at " << dist[v] << " ? " << col[v] << endl;
		if(v == V) return dist[v];
		for(auto [i, w] : g[v]) {
			//cout << v << " -> " << i << " " << w << endl;
			enq(i, di+w);
		}
	}
	//for(int i = 0; i < g.size(); i++) cout << col[i] << " "; cout << endl;
	//for(int i = 0; i < g.size(); i++) cout << dist[i] << " "; cout << endl;
	return -1;
}

Compilation message

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:32:30: warning: narrowing conversion of 'g.std::vector<std::vector<std::array<int, 2> > >::size()' from 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   32 |    g.back().push_back({g.size(), y[id]-loh});
      |                        ~~~~~~^~
walk.cpp:33:26: warning: narrowing conversion of '(g.std::vector<std::vector<std::array<int, 2> > >::size() - 1)' from 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   33 |    g.push_back({{g.size()-1, y[id]-loh}});
      |                  ~~~~~~~~^~
walk.cpp:38:35: warning: narrowing conversion of '(g.std::vector<std::vector<std::array<int, 2> > >::size() - 1)' from 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   38 |     g[lst[id]].push_back({g.size()-1, x[i]-x[col[lst[id]]]});
      |                           ~~~~~~~~^~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 264 ms 62836 KB Output is correct
4 Correct 423 ms 74040 KB Output is correct
5 Correct 290 ms 64420 KB Output is correct
6 Correct 255 ms 58728 KB Output is correct
7 Correct 260 ms 64620 KB Output is correct
8 Correct 355 ms 81520 KB Output is correct
9 Correct 312 ms 66700 KB Output is correct
10 Correct 581 ms 114752 KB Output is correct
11 Correct 197 ms 40288 KB Output is correct
12 Correct 165 ms 37348 KB Output is correct
13 Correct 488 ms 91672 KB Output is correct
14 Correct 172 ms 36708 KB Output is correct
15 Incorrect 180 ms 37256 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 12248 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 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -