| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1023895 |
2024-07-15T09:02:40 Z |
c2zi6 |
Sky Walking (IOI19_walk) |
C++14 |
|
4000 ms |
518400 KB |
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "walk.h"
struct BRIDGE {
int l, r, y;
};
struct BUILDING {
int x, h;
};
namespace TEST4 {
struct SEGTREE {
int n;
VI tree;
VI lazy;
SEGTREE(int sz) {
n = 1;
while (n < sz) n *= 2;
lazy = tree = VI(2*n, -1);
}
void push(int N) {
if (lazy[N] == -1) return;
tree[N] = lazy[N];
if (N <= n-2) {
lazy[2*N+1] = lazy[N];
lazy[2*N+2] = lazy[N];
}
lazy[N] = -1;
}
int get(int N, int L, int R, int l, int r) {
push(N);
if (l <= L && R <= r) return tree[N];
if (R < l || L > r) return -1;
int M = (L + R) / 2;
return max(get(2*N+1, L, M, l, r), get(2*N+2, M+1, R, l, r));
}
void upd(int N, int L, int R, int l, int r, int s) {
push(N);
if (R < l || L > r) return;
if (l <= L && R <= r) {
lazy[N] = s;
push(N);
return;
}
int M = (L + R) / 2;
upd(2*N+1, L, M, l, r, s);
upd(2*N+2, M+1, R, l, r, s);
tree[N] = max(tree[2*N+1], tree[2*N+2]);
}
int get(int l, int r) {
return get(0, 0, n-1, l, r);
}
int get(int i) {
return get(0, 0, n-1, i, i);
}
void upd(int l, int r, int s) {
upd(0, 0, n-1, l, r, s);
}
};
};
ll min_distance(VI X, VI H, VI L, VI R, VI Y, int S, int T) {
vector<BUILDING> buildings(X.size());
rep(i, X.size()) buildings[i] = {X[i], H[i]};
vector<BRIDGE> bridges(L.size());
rep(i, L.size()) bridges[i] = {L[i], R[i], Y[i]};
map<PII, int> ind;
VPI point;
VVPI gp;
auto addvertex = [&](int x, int y) {
if (ind.count({x, y})) return;
ind[{x, y}] = gp.size();
point.pb({x, y});
gp.pb(VPI());
};
if (S == 0 && T == X.size()-1 && false) {
/*TEST 4 */
addvertex(0, 0);
addvertex(X.size()-1, 0);
/* vertical */
sort(all(bridges), [](const BRIDGE& a, const BRIDGE& b){return a.y < b.y;});
TEST4::SEGTREE seg(X.size());
seg.upd(0, 0, 0);
seg.upd(X.size()-1, X.size()-1, 0);
for (auto&[l, r, y] : bridges) {
addvertex(l, y);
addvertex(r, y);
for (int x : {l, r}) {
int vy = seg.get(x);
if (vy == -1) continue;
addvertex(x, vy);
int u = ind[{x, y}];
int v = ind[{x, vy}];
int w = y - vy;
gp[u].pb({v, w});
gp[v].pb({u, w});
}
seg.upd(l, r, y);
}
/* horizontal */
VPI pts = point;
sort(all(pts), [](const PII& a, const PII& b){return mkp(a.ss, a.ff) < mkp(b.ss, b.ff);});
rep(i, pts.size()-1) {
if (pts[i].ss == 0) continue;
if (pts[i].ss != pts[i+1].ss) continue;
int u = ind[pts[i]];
int v = ind[pts[i+1]];
int w = X[pts[i+1].ff] - X[pts[i].ff];
gp[u].pb({v, w});
gp[v].pb({u, w});
}
} else {
/* TEST 1, 2 */
addvertex(X[S], 0);
addvertex(X[T], 0);
for (auto&[a, b, c] : bridges) a = X[a], b = X[b];
sort(all(buildings), [](const BUILDING& a, const BUILDING& b){return a.h > b.h;});
sort(all(bridges), [](const BRIDGE& a, const BRIDGE& b){return a.y > b.y;});
/* horizontal */
set<int> st;
for (int j = 0, i = 0; i < bridges.size(); i++) {
auto&[l, r, y] = bridges[i];
while (j < buildings.size() && buildings[j].h >= y) st.insert(buildings[j++].x);
VI xs;
for (auto it = st.lower_bound(l); it != st.end() && *it <= r; it++) xs.pb(*it);
for (int x : xs) addvertex(x, y);
rep(i, xs.size()-1) {
int u = ind[{xs[i], y}];
int v = ind[{xs[i+1], y}];
int w = xs[i+1]-xs[i];
gp[u].pb({v, w});
gp[v].pb({u, w});
}
}
/* vertical */
VPI pts = point;
sort(all(pts));
rep(i, pts.size()-1) {
if (pts[i].ff != pts[i+1].ff) continue;
int u = ind[pts[i]];
int v = ind[pts[i+1]];
int w = pts[i+1].ss - pts[i].ss;
gp[u].pb({v, w});
gp[v].pb({u, w});
}
}
int n = gp.size();
priority_queue<PLL> pq;
VL dist(n, 1e18);
VI vis(n);
pq.push({0, 0});
dist[0] = 0;
while (pq.size()) {
int u = pq.top().ss;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto[v, w] : gp[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
return dist[1];
}
Compilation message
walk.cpp: In function 'll min_distance(VI, VI, VI, VI, VI, int, int)':
walk.cpp:106:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | if (S == 0 && T == X.size()-1 && false) {
| ~~^~~~~~~~~~~~~
walk.cpp:115:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
115 | for (auto&[l, r, y] : bridges) {
| ^
walk.cpp:146:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
146 | for (auto&[a, b, c] : bridges) a = X[a], b = X[b];
| ^
walk.cpp:151:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<BRIDGE>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for (int j = 0, i = 0; i < bridges.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
walk.cpp:152:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
152 | auto&[l, r, y] = bridges[i];
| ^
walk.cpp:153:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<BUILDING>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | while (j < buildings.size() && buildings[j].h >= y) st.insert(buildings[j++].x);
| ~~^~~~~~~~~~~~~~~~~~
walk.cpp:189:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
189 | for (auto[v, w] : gp[u]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
432 KB |
Output is correct |
| 3 |
Correct |
0 ms |
436 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
432 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1128 ms |
116468 KB |
Output is correct |
| 4 |
Correct |
1044 ms |
123180 KB |
Output is correct |
| 5 |
Correct |
733 ms |
106040 KB |
Output is correct |
| 6 |
Correct |
636 ms |
93772 KB |
Output is correct |
| 7 |
Incorrect |
717 ms |
106104 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
13184 KB |
Output is correct |
| 2 |
Execution timed out |
4106 ms |
518400 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
13184 KB |
Output is correct |
| 2 |
Execution timed out |
4106 ms |
518400 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
432 KB |
Output is correct |
| 3 |
Correct |
0 ms |
436 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
