| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 436525 |
2021-06-24T15:02:53 Z |
rqi |
Sky Walking (IOI19_walk) |
C++14 |
|
191 ms |
195172 KB |
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;
typedef vector<ll> vl;
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define bk back()
#define ins insert
#define lb lower_bound
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
const ll INF = 1e18;
int n, m;
const int mx = 2000005;
vector<pair<int, ll>> adj[mx];
ll dij[mx];
ll solveShort(int N, int A, int B){
for(int i = 0; i < N; i++){
dij[i] = INF;
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
dij[A] = 0;
pq.push(mp(dij[A], A));
while(sz(pq)){
ll d = pq.top().f;
int node = pq.top().s;
pq.pop();
if(dij[node] < d) continue;
for(auto u: adj[node]){
ll new_d = d+u.s;
if(dij[u.f] <= new_d) continue;
dij[u.f] = new_d;
pq.push(mp(dij[u.f], u.f));
}
}
if(dij[B] == INF) return -1;
return dij[B];
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
n = sz(x);
m = sz(l);
if(s == 0 && g == n-1){
cout << "HI" << "\n";
cout.flush();
vi ending_at[mx];
for(int i = 0; i < m; i++){
ending_at[r[i]].pb(i);
}
vi starting_at[mx];
for(int i = 0; i < m; i++){
starting_at[l[i]].pb(i);
}
ending_at[0].pb(m);
starting_at[n-1].pb(m+1);
l.pb(0);
r.pb(0);
l.pb(n-1);
r.pb(n-1);
y.pb(0);
y.pb(0);
vector<pair<pi, ll>> eds;
set<pi> cur_sky_heights; // height, sky index
cur_sky_heights.ins(mp(m, y[m]));
for(int i = 0; i < n; i++){
//do updates
for(auto sky: ending_at[i]){
cur_sky_heights.erase(mp(y[sky], sky));
}
for(auto sky: starting_at[i]){
cur_sky_heights.ins(mp(y[sky], sky));
}
for(auto sky: ending_at[i]){
auto it_above = cur_sky_heights.lb(mp(y[sky], 0));
auto it_below = cur_sky_heights.lb(mp(y[sky]+1, 0));
if(it_above != cur_sky_heights.end()){
int to_sky = it_above->s;
eds.pb(mp(mp(sky, to_sky), abs(y[sky]-y[to_sky])));
}
if(it_below != cur_sky_heights.begin()){
it_below = prev(it_below);
int to_sky = it_below->s;
eds.pb(mp(mp(sky, to_sky), abs(y[sky]-y[to_sky])));
}
}
}
for(auto u: eds){
adj[u.f.f].pb(mp(u.f.s, u.s));
}
//m is source, m+1 is sink
return solveShort(m+2, m, m+1);
}
vi sort_by_y;
for(int i = 0; i < m; i++){
sort_by_y.pb(i);
}
sort(all(sort_by_y), [&](const int& a, const int& b){
return y[a] > y[b];
});
vi sort_by_h;
for(int i = 0; i < n; i++){
sort_by_h.pb(i);
}
sort(all(sort_by_h), [&](const int& a, const int& b){
return h[a] > h[b];
});
set<int> active_buildings;
int sort_by_h_ind = 0;
vector<pair<pi, pi>> point_eds; //building index, height
// cout << "HI" << "\n";
// cout.flush();
for(auto sky: sort_by_y){
while(sort_by_h_ind < sz(sort_by_h)){
int building_ind = sort_by_h[sort_by_h_ind];
if(h[building_ind] >= y[sky]){
active_buildings.ins(building_ind);
sort_by_h_ind++;
}
else{
break;
}
}
auto it = active_buildings.lb(l[sky]);
assert(*it == l[sky]);
while(true){
assert(next(it) != active_buildings.end());
point_eds.pb(mp(mp(*it, y[sky]), mp(*next(it), y[sky])));
if(*next(it) == r[sky]) break;
it = next(it);
}
}
// cout << "HI" << "\n";
// cout.flush();
set<int> each_building[mx]; //sky walk heights for each building
for(auto u: point_eds){
// cout << u.f.f << " " << u.f.s << " " << u.s.f << " " << u.s.s << "\n";
each_building[u.f.f].ins(u.f.s);
each_building[u.s.f].ins(u.s.s);
}
for(int i = 0; i < n; i++){
each_building[i].ins(0);
each_building[i].ins(h[i]);
}
for(int i = 0; i < n; i++){
auto it = each_building[i].begin();
while(next(it) != each_building[i].end()){
int y1 = *it;
int y2 = *next(it);
point_eds.pb(mp(mp(i, y1), mp(i, y2)));
it = next(it);
}
}
map<pi, int> compress;
vpi all_nodes;
for(auto u: point_eds){
all_nodes.pb(u.f);
all_nodes.pb(u.s);
}
int cnt = 0;
for(auto u: all_nodes){
if(!compress.count(u)){
compress[u] = cnt;
cnt++;
}
}
// for(auto u: point_eds){
// cout << u.f.f << " " << u.f.s << " " << u.s.f << " " << u.s.s << "\n";
// }
for(auto u: point_eds){
ll dist = INF;
if(u.f.f == u.s.f){
dist = abs(u.s.s-u.f.s);
}
else{
assert(u.s.s == u.f.s);
dist = abs(x[u.s.f]-x[u.f.f]);
}
int a = compress[u.f];
int b = compress[u.s];
adj[a].pb(mp(b, dist));
adj[b].pb(mp(a, dist));
// cout << a << " " << b << " " << dist << "\n";
}
return solveShort(cnt, compress[mp(s, 0)], compress[mp(g, 0)]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
188088 KB |
Output is correct |
| 2 |
Incorrect |
152 ms |
188056 KB |
secret mismatch |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
188100 KB |
Output is correct |
| 2 |
Incorrect |
119 ms |
188060 KB |
secret mismatch |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
191 ms |
195172 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
191 ms |
195172 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
188088 KB |
Output is correct |
| 2 |
Incorrect |
152 ms |
188056 KB |
secret mismatch |
| 3 |
Halted |
0 ms |
0 KB |
- |
