Submission #417253

#TimeUsernameProblemLanguageResultExecution timeMemory
417253Kevin_Zhang_TWSky Walking (IOI19_walk)C++17
100 / 100
2268 ms274384 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); } template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); } #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; } #else #define DE(...) 0 #define debug(...) 0 #endif // TODO Watch out for the size const int MAX_N = 400010 * 10; const ll inf = 1ll << 55; #include "walk.h" // graph is 0 based int n, m; vector<int> xup[MAX_N]; vector<int> x, h, pfsz; vector<pair<int,int>> edge[MAX_N]; int get_id(int i, int j) { assert(binary_search(AI(xup[i]), j)); return lower_bound(AI(xup[i]), j) - begin(xup[i]) + pfsz[i]; } const int C = MAX_N; void sweep(vector<int> l, vector<int> r, vector<int> y) { set<int> ally; vector<vector<int>> in(n + 10), out(n + 10); for (int i = 0;i < m;++i) { if (r[i] - l[i] + 1 <= 2) continue; DE(l[i], r[i], y[i]); in[l[i]+1].pb(y[i]); out[r[i]].pb(y[i]); } for (int i = 0;i < n;++i) { for (int j : out[i]) ally.erase(j); for (int j : in[i]) ally.insert(j); vector<int> ep = xup[i]; if (false && ep.size() && ep[0] == 0) { xup[i].insert(end(xup[i]), AI(ally)); continue; } // auto it = begin(ally), rit = ally.upper_bound(h[i]); // for (int j = 0;j < C && it != rit;++j) { // xup[i].pb(*it++); // } // for (int j = 0;j < C && it != rit;++j) // xup[i].pb(*--rit); ep.pb(0), ep.pb(h[i]); for (int j : ep) { auto it = ally.upper_bound(j); { auto c = it; if (c != end(ally)) xup[i].pb(*c++); //if (c != end(ally)) xup[i].pb(*c++); } //if (it != begin(ally)) xup[i].pb(*prev(it)), --it; if (it != begin(ally)) xup[i].pb(*prev(it)); } } } void init_ver(std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) { // for (int i = 0;i < m;++i) { // for (int j = l[i];j <= r[i];++j) { // if (h[j] < y[i]) continue; // xup[j].pb(y[i]); // } // } // for (int i = 0;i < n;++i) { // sort(AI(xup[i])); // xup[i].erase(unique(AI(xup[i])), end(xup[i])); // if (xup[i].size() < C * 2) continue; // vector<int> e(end(xup[i])-C, end(xup[i])); // xup[i].resize(C); // xup[i].insert(end(xup[i]), AI(e)); // } // xup[s].pb(0), xup[g].pb(0); for (int i = 0;i < m;++i) { xup[ l[i] ].pb( y[i] ); xup[ r[i] ].pb( y[i] ); } sweep(l, r, y); pfsz.resize(n+1); for (int i = 0;i < n;++i) { sort(AI(xup[i])); xup[i].erase(unique(AI(xup[i])), end(xup[i])); while (xup[i].size() && xup[i].back() > h[i]) xup[i].pop_back(); pfsz[i+1] = pfsz[i] + xup[i].size(); for (int j = 1;j < xup[i].size();++j) { int a = pfsz[i]+j-1, b = pfsz[i] + j //int a = get_id(i, xup[i][j-1]), b = get_id(i, xup[i][j]), , d = xup[i][j] - xup[i][j-1]; edge[a].pb(b, d); edge[b].pb(a, d); } } } void mbuild(vector<int> l, vector<int> r, vector<int> y) { map<int, vector<int>> xs; for (int i = 0;i < n;++i) { for (int j : xup[i]) xs[j].pb(i); } for (int i = 0;i < m;++i) { vector< int > loc; auto it = lower_bound(AI( xs[y[i]] ), l[i]); while (it != end(xs[y[i]])) { if (*it > r[i]) break; loc.pb(*it++); } for (int j = 1;j < loc.size();++j) { int a = get_id(loc[j-1], y[i]), b = get_id(loc[j], y[i]), d = x[ loc[j] ] - x[ loc[j-1] ]; edge[a].pb(b, d); edge[b].pb(a, d); } } } ll sho(int s, int t) { int V = pfsz.back() + 10; vector<ll> dis(V, inf); priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq; auto upd = [&](int id, ll d) { if (chmin(dis[id], d)) pq.emplace(d, id); }; upd(s, 0); while (pq.size()) { auto [d, x] = pq.top(); pq.pop(); if (d != dis[x]) continue; if (x == t) return d; DE(x, d); for (auto [u, w] : edge[x]) upd(u, d + w); } return -1; } 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) { n = x.size(); m = l.size(); ::x = x; ::h = h; init_ver(l, r, y, s, g); mbuild(l, r, y); return sho( get_id(s, 0), get_id(g, 0) ); }

Compilation message (stderr)

walk.cpp: In function 'void sweep(std::vector<int>, std::vector<int>, std::vector<int>)':
walk.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
walk.cpp:43:3: note: in expansion of macro 'DE'
   43 |   DE(l[i], r[i], y[i]);
      |   ^~
walk.cpp: In function 'void init_ver(std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for (int j = 1;j < xup[i].size();++j) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void mbuild(std::vector<int>, std::vector<int>, std::vector<int>)':
walk.cpp:141:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for (int j = 1;j < loc.size();++j) {
      |                  ~~^~~~~~~~~~~~
walk.cpp: In function 'll sho(int, int)':
walk.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
walk.cpp:167:3: note: in expansion of macro 'DE'
  167 |   DE(x, d);
      |   ^~
#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...