제출 #373139

#제출 시각아이디문제언어결과실행 시간메모리
373139KanonSky Walking (IOI19_walk)C++14
0 / 100
4072 ms271080 KiB
#include <bits/stdc++.h> using namespace std; template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template <size_t N> string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__); struct edge { int t; int dis; edge(int _t, int _dis) : t(_t), dis(_dis){}; }; vector<long long> calc(int n, int s, int t, vector<vector<edge>> g) { vector<long long> ret(n, LLONG_MAX); ret[s] = 0; set<pair<long long, int>> que; vector<int> was(n); que.insert({ret[s], s}); while(que.size()) { int v = que.begin()->second; que.erase(que.begin()); if(was[v]) continue; was[v] = 1; for(edge e : g[v]) { int u = e.t; if(ret[u] > ret[v] + e.dis) { ret[u] = ret[v] + e.dis; que.insert(make_pair(ret[u], u)); } } } return ret; } template <typename T, class F = function<T(const T&, const T&)>> class SparseTable { public: int n; vector<vector<T>> mat; F func; SparseTable(const vector<T>& a, const F& f) : func(f) { n = static_cast<int>(a.size()); int max_log = 32 - __builtin_clz(n); mat.resize(max_log); mat[0] = a; for (int j = 1; j < max_log; j++) { mat[j].resize(n - (1 << j) + 1); for (int i = 0; i <= n - (1 << j); i++) { mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]); } } } T get(int from, int to) const { assert(0 <= from && from <= to && to <= n - 1); int lg = 32 - __builtin_clz(to - from + 1) - 1; return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]); } }; long long min_distance(vector<int> px, vector<int> h, vector<int> l, vector<int> r, vector<int> py, int s, int t) { int n = px.size(); int m = py.size(); set<pair<int, int>> p; auto add = [&](int x, int y) { p.insert(make_pair(x, y)); }; add(px[s], 0); add(px[t], 0); for(int i = 0; i < m; i++) { add(px[l[i]], py[i]); add(px[r[i]], py[i]); } SparseTable<int> d(h, [&](int i, int j){return max(i, j);}); auto find_left = [&](int l, int r, int y) { if(d.get(l, r) < y) return -1; while(r - l >= 1) { int mid = (r + l) >> 1; if(d.get(l, mid) < y) l = mid + 1; else r = mid; } return r; }; auto find_right = [&](int l, int r, int y) { if(d.get(l, r) < y) return -1; while(r - l >= 1) { int mid = (r + l) >> 1; if(d.get(mid + 1, r) < y) r = mid; else l = mid + 1; } return r; }; for(int i = 0; i < m; i++) { int y = py[i]; for(int rot = 0; rot < 2; rot++) { if(l[i] < s && s < r[i]) { int ll = find_right(l[i], s, y); int rr = find_left(s, r[i], y); if(ll != -1) add(px[ll], y); if(rr != -1) add(px[rr], y); } swap(s, t); } } vector<pair<int, int>> ad; { for(auto pp : p) { int x = pp.first, y = pp.second; int id = lower_bound(px.begin(), px.end(), x) - px.begin(); if(id < n - 1) { int ll = find_left(id + 1, n - 1, y); if(ll != -1) ad.emplace_back(px[ll], y); } if(id > 0) { int rr = find_right(0, id - 1, y); if(rr != -1) ad.emplace_back(px[rr], y); } } } { vector<vector<int>> inc(n); vector<vector<int>> rev(n); for(int i = 0; i < m; i++) { inc[l[i]].push_back(i); if(r[i] < n - 1) rev[r[i] + 1].push_back(i); } int cur = 0; map<int, int> Y; for(auto pp : p) { int x = pp.first, y = pp.second; while(cur < n && px[cur] <= x) { for(int i : rev[cur]) { Y[py[i]]--; if(Y[py[i]] == 0) Y.erase(py[i]); } for(int i : inc[cur]) Y[py[i]]++; cur++; } auto it = Y.find(y); if(it == Y.end()) continue; if(it != Y.begin()) ad.emplace_back(x, prev(it)->first); if(it != prev(Y.end())) ad.emplace_back(x, next(it)->first); } } for(auto i : ad) add(i.first, i.second); //numerate int sz = p.size(); map<pair<int, int>, int> id; for(auto i : p) { int fp = id.size(); id[i] = fp; } vector<vector<edge>> g(sz); // add ver edged int cnt = 0; for(auto it = p.begin(); next(it) != p.end(); it++) { if(it->first == next(it)->first) { int u = cnt; int v = cnt + 1; int dis = abs(it->second - next(it)->second); g[u].emplace_back(v, dis); g[v].emplace_back(u, dis); } cnt++; } // add hor edge map<int, vector<int>> Y; for(auto i : p) Y[i.second].push_back(i.first); for(int i = 0; i < m; i++) { int y = py[i]; int L = px[l[i]]; int R = px[r[i]]; for(int j = lower_bound(Y[y].begin(), Y[y].end(), L) - Y[y].begin(); Y[y][j] < R; j++) { int u = id[make_pair(Y[y][j], y)]; int v = id[make_pair(Y[y][j + 1], y)]; int dis = abs(Y[y][j] - Y[y][j + 1]); g[u].emplace_back(v, dis); g[v].emplace_back(u, dis); } } // int ss = id[make_pair(px[s], 0)]; int tt = id[make_pair(px[t], 0)]; vector<long long> ret = calc(sz, ss, tt, g); if(ret[tt] == LLONG_MAX) return -1; return ret[tt]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...