| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 416741 |
2021-06-02T21:25:42 Z |
peuch |
Sky Walking (IOI19_walk) |
C++17 |
|
4000 ms |
200152 KB |
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5 + 10;
const long long INF = 1e18;
map<pair<long long, long long>, long long> node;
vector<long long> dist;
vector<bool> marc;
vector<vector<long long> > ar, wg;
long long cnt = -1;
struct event{
long long l, r, h;
event(long long _l = 0, long long _r = 0, long long _h = 0){
l = _l, r = _r, h = _h;
}
bool operator < (event x) const {
if(h == x.h) return r - l < x.l - x.r;
return h > x.h;
}
};
vector<event> line;
void dijkstra(long long ini);
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(long long i = 0; i < X.size(); i++)
line.push_back(event(i, i, H[i]));
for(long long i = 0; i < L.size(); i++)
line.push_back(event(L[i], R[i], Y[i]));
sort(line.begin(), line.end());
vector<long long> last(X.size(), 0);
set<long long> torres;
for(long long i = 0; i < line.size(); i++){
long long l = line[i].l, r = line[i].r, y = line[i].h;
if(l == r) torres.insert(l);
else{
set<long long> :: iterator it = torres.lower_bound(l);
if(node[make_pair(*it, y)] == 0) {
node[make_pair(*it, 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[*it] != 0) {
ar[node[make_pair(*it, y)]].push_back(node[make_pair(*it, last[*it])]);
ar[node[make_pair(*it, last[*it])]].push_back(node[make_pair(*it, y)]);
wg[node[make_pair(*it, y)]].push_back(abs(y - last[*it]));
wg[node[make_pair(*it, last[*it])]].push_back(abs(y - last[*it]));
}
last[*it] = y;
}
long long ult = *it;
it++;
while(it != torres.end() && *it <= r){
if(node[make_pair(*it, y)] == 0) {
node[make_pair(*it, 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[*it] != 0) {
ar[node[make_pair(*it, y)]].push_back(node[make_pair(*it, last[*it])]);
ar[node[make_pair(*it, last[*it])]].push_back(node[make_pair(*it, y)]);
wg[node[make_pair(*it, y)]].push_back(abs(y - last[*it]));
wg[node[make_pair(*it, last[*it])]].push_back(abs(y - last[*it]));
}
last[*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(long long i = 0; i < X.size(); i++){
if(node[make_pair(i, 0)] == 0) {
node[make_pair(i, 0)] = ++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[i] != 0) {
ar[node[make_pair(i, 0)]].push_back(node[make_pair(i, last[i])]);
ar[node[make_pair(i, last[i])]].push_back(node[make_pair(i, 0)]);
wg[node[make_pair(i, 0)]].push_back(abs(0 - last[i]));
wg[node[make_pair(i, last[i])]].push_back(abs(0 - last[i]));
}
last[i] = 0;
}
}
dijkstra(node[make_pair(S, 0)]);
if(dist[node[make_pair(G, 0)]] >= INF) dist[node[make_pair(G, 0)]] = -1;
return dist[node[make_pair(G, 0)]];
}
void dijkstra(long long ini){
dist[ini] = 0;
set<pair<long long, long long> > s;
for(long long i = 0; i <= cnt; i++)
s.insert(make_pair(dist[i], i));
while(!s.empty()){
long long cur = s.begin()->second;
if(dist[cur] >= INF) break;
marc[cur] = 1;
s.erase(s.begin());
for(long long i = 0; i < ar[cur].size(); i++){
long long 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 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:30:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(long long i = 0; i < X.size(); i++)
| ~~^~~~~~~~~~
walk.cpp:32:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(long long i = 0; i < L.size(); i++)
| ~~^~~~~~~~~~
walk.cpp:37:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(long long i = 0; i < line.size(); i++){
| ~~^~~~~~~~~~~~~
walk.cpp:83:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(long long i = 0; i < X.size(); i++){
| ~~^~~~~~~~~~
walk.cpp: In function 'void dijkstra(long long int)':
walk.cpp:114:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(long long i = 0; i < ar[cur].size(); i++){
| ~~^~~~~~~~~~~~~~~~
| # |
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 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
2 ms |
460 KB |
Output is correct |
| 7 |
Correct |
2 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
3 ms |
460 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Execution timed out |
4062 ms |
200152 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4062 ms |
3272 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4062 ms |
3272 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
2 ms |
460 KB |
Output is correct |
| 7 |
Correct |
2 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
3 ms |
460 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
