| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 416758 |
2021-06-02T21:51:48 Z |
peuch |
Sky Walking (IOI19_walk) |
C++17 |
|
0 ms |
0 KB |
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const long long INF = 1e18;
map<pair<int, int>, int> node;
vector<long long> dist;
vector<bool> marc;
vector<vector<int> > ar, wg;
long long cnt = -1;
struct event{
int l, r, h;
event(int _l = 0, int _r = 0, int _h = 0){
l = _l, r = _r, h = _h;
}
bool operator < (event x) const {
if(h == x.h) return r - l < x.r - x.l;
return h > x.h;
}
};
vector<event> line;
vector<int> last;
void dijkstra(int ini);
int create(int x, int y){
if(node[make_pair(x, y)] != 0) return node[make_pair(x, y)];
node[make_pair(x, y)] = ++cnt;
ar.push_back(vector<long long>(0));
wg.push_back(vector<long long>(0));
dist.push_back(INF);
marc.push_back(0);
if(last[x] != 0) {
ar[node[make_pair(x, y)]].push_back(node[make_pair(x, last[x])]);
ar[node[make_pair(x, last[x])]].push_back(node[make_pair(x, y)]);
wg[node[make_pair(x, y)]].push_back(abs(y - last[x]));
wg[node[make_pair(x, last[x])]].push_back(abs(y - last[x]));
}
last[x] = y;
}
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) {
for(int i = 0; i < X.size(); i++)
line.push_back(event(i, i, H[i]));
for(int i = 0; i < L.size(); i++)
line.push_back(event(L[i], R[i], Y[i]));
sort(line.begin(), line.end());
last = vector<int> (X.size(), 0);
set<int> torres;
for(int i = 0; i < line.size(); i++){
int l = line[i].l, r = line[i].r, y = line[i].h;
if(l == r) torres.insert(l);
else{
set<int> :: iterator it = torres.upper_bound(l);
create(l, y);
int ult = l;
while(it != torres.end() && *it <= r){
create(*it, y);
ar[node[make_pair(*it, y)]].push_back(node[make_pair(ult, y)]);
ar[node[make_pair(ult, y)]].push_back(node[make_pair(*it, y)]);
wg[node[make_pair(*it, y)]].push_back(abs(X[*it] - X[ult]));
wg[node[make_pair(ult, y)]].push_back(abs(X[*it] - X[ult]));
ult = *it;
it++;
}
}
}
for(int i = 0; i < X.size(); i++)
create(i, 0);
dijkstra(create(S, 0));
if(dist[create(G, 0)] >= INF) dist[create(G, 0)] = -1;
return dist[create(G, 0)];
}
void dijkstra(int ini){
dist[ini] = 0;
set<pair<long long, int> > s;
for(int i = 0; i <= cnt; i++)
s.insert(make_pair(dist[i], i));
while(!s.empty()){
int cur = s.begin()->second;
if(dist[cur] >= INF) break;
marc[cur] = 1;
s.erase(s.begin());
for(int i = 0; i < ar[cur].size(); i++){
int viz = ar[cur][i];
if(marc[viz]) continue;
s.erase(make_pair(dist[viz], viz));
dist[viz] = min(dist[viz], dist[cur] + wg[cur][i]);
s.insert(make_pair(dist[viz], viz));
}
}
}
Compilation message
walk.cpp: In function 'int create(int, int)':
walk.cpp:33:35: error: no matching function for call to 'std::vector<std::vector<int> >::push_back(std::vector<long long int>)'
33 | ar.push_back(vector<long long>(0));
| ^
In file included from /usr/include/c++/10/vector:67,
from walk.h:4,
from walk.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]'
1187 | push_back(const value_type& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note: no known conversion for argument 1 from 'std::vector<long long int>' to 'const value_type&' {aka 'const std::vector<int>&'}
1187 | push_back(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]'
1203 | push_back(value_type&& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note: no known conversion for argument 1 from 'std::vector<long long int>' to 'std::vector<std::vector<int> >::value_type&&' {aka 'std::vector<int>&&'}
1203 | push_back(value_type&& __x)
| ~~~~~~~~~~~~~^~~
walk.cpp:34:35: error: no matching function for call to 'std::vector<std::vector<int> >::push_back(std::vector<long long int>)'
34 | wg.push_back(vector<long long>(0));
| ^
In file included from /usr/include/c++/10/vector:67,
from walk.h:4,
from walk.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]'
1187 | push_back(const value_type& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note: no known conversion for argument 1 from 'std::vector<long long int>' to 'const value_type&' {aka 'const std::vector<int>&'}
1187 | push_back(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]'
1203 | push_back(value_type&& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note: no known conversion for argument 1 from 'std::vector<long long int>' to 'std::vector<std::vector<int> >::value_type&&' {aka 'std::vector<int>&&'}
1203 | push_back(value_type&& __x)
| ~~~~~~~~~~~~~^~~
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:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i = 0; i < X.size(); i++)
| ~~^~~~~~~~~~
walk.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i = 0; i < L.size(); i++)
| ~~^~~~~~~~~~
walk.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0; i < line.size(); i++){
| ~~^~~~~~~~~~~~~
walk.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < X.size(); i++)
| ~~^~~~~~~~~~
walk.cpp: In function 'void dijkstra(int)':
walk.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i = 0; i < ar[cur].size(); i++){
| ~~^~~~~~~~~~~~~~~~
walk.cpp: In function 'int create(int, int)':
walk.cpp:43:10: warning: control reaches end of non-void function [-Wreturn-type]
43 | last[x] = y;
