oj.uz

Submission #433879

# Submission time Handle Problem Language Result Execution time Memory
433879 2021-06-20T11:48:19 Z kostia244 Sky Walking (IOI19_walk) C++17
0 / 100
 454 ms 86148 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]]]});
      |                           ~~~~~~~~^~
walk.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i = 0; i < g.size(); i++) cout << col[i] << " "; cout << endl;
      |                 ~~^~~~~~~~~~
walk.cpp:68:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   68 |  for(int i = 0; i < g.size(); i++) cout << col[i] << " "; cout << endl;
      |  ^~~
walk.cpp:68:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   68 |  for(int i = 0; i < g.size(); i++) cout << col[i] << " "; cout << endl;
      |                                                           ^~~~
walk.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i = 0; i < g.size(); i++) cout << dist[i] << " "; cout << endl;
      |                 ~~^~~~~~~~~~
walk.cpp:69:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   69 |  for(int i = 0; i < g.size(); i++) cout << dist[i] << " "; cout << endl;
      |  ^~~
walk.cpp:69:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   69 |  for(int i = 0; i < g.size(); i++) cout << dist[i] << " "; cout << endl;
      |                                                            ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 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 296 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 264 ms 64876 KB Output is correct
4 Correct 432 ms 78080 KB Output is correct
5 Correct 280 ms 67996 KB Output is correct
6 Correct 254 ms 62196 KB Output is correct
7 Incorrect 454 ms 86148 KB secret mismatch
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 15868 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 15868 KB secret mismatch
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 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -