Submission #831639

#TimeUsernameProblemLanguageResultExecution timeMemory
831639Red_InsideSky Walking (IOI19_walk)C++17
10 / 100
4093 ms677056 KiB
#include <bits/stdc++.h> using namespace std; #define forn(j, i, n) for(int i = j; i <= n; ++i) #define FOR(j, i, n) for(int i = j; i < n; ++i) #define pb push_back #define f first #define s second #define all(v) v.begin(), v.end() #define nfor(j, i, n) for(int i = n; i >= j; --i) #define ll long long //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //const int maxn=2e5+10; #define o cout <<"BUG\n"; #define pii pair <int, int> using namespace std; const int maxn = 1e5+10; ll n, m, x[maxn], y[maxn], h[maxn], l[maxn], r[maxn]; vector <ll> dot[maxn], ver[maxn]; long long min_distance(vector<int> X, vector<int> H, vector<int> L2, vector<int> R2, vector<int> Y2, int s, int g) { m = L2.size(); s++, g++; forn(1, i, m) { l[i] = L2[i-1]+1; r[i] = R2[i-1]+1; y[i] = Y2[i-1]; } n = X.size(); forn(1, i, n) { x[i] = X[i-1]; h[i] = H[i-1]; } forn(1, i, m) { forn(l[i], j, r[i]) { if(h[j] >= y[i]) dot[j].pb(y[i]); } } int cnt = 0; forn(1, i, n) { dot[i].pb(0); sort(all(dot[i])); dot[i].erase(unique(all(dot[i])), dot[i].end()); ver[i].assign(dot[i].size(), 0); FOR(0, j, dot[i].size()) ver[i][j] = ++cnt; } vector <vector <pair <ll, ll> > > edge; edge.assign(cnt+10, {}); forn(1, i, n) { FOR(1, j, dot[i].size()) { edge[ver[i][j]].pb({ver[i][j-1], dot[i][j]-dot[i][j-1]}); edge[ver[i][j-1]].pb({ver[i][j], dot[i][j]-dot[i][j-1]}); } } forn(1, i, m) { int last = -1; int indx = 0; forn(l[i], j, r[i]) { if(h[j] < y[i]) continue; int se = lower_bound(all(dot[j]), y[i]) - dot[j].begin(); int nw = ver[j][se]; if(last != -1) { edge[last].pb({nw, x[j]-x[indx]}); edge[nw].pb({last, x[j]-x[indx]}); } indx = j; last = nw; } } /* forn(1, i, n) { cout << " FOR " << i << endl; FOR(0, j, dot[i].size()) cout << dot[i][j] << " " << ver[i][j] << endl; cout << endl; }*/ // forn(1, i, cnt) // for(auto j : edge[i]) cout << i << " " << j.f << " " << j.s << endl; ll inf = 1e18; vector <ll> dist(cnt+12); forn(1, i, cnt) { dist[i] = inf; } int v = ver[s][0]; dist[v] = 0; set <pair <ll, int> > st; st.insert({0, v}); while(st.size()) { int v = st.begin()->s; st.erase(st.begin()); for(auto to : edge[v]) { if(dist[to.f] > dist[v] + to.s) { st.erase({dist[to.f], to.f}); dist[to.f] = dist[v]+to.s; st.insert({dist[to.f], to.f}); } } } if(dist[ver[g][0]] == inf) return -1; return dist[ver[g][0]]; }

Compilation message (stderr)

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:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(j, i, n) for(int i = j; i < n; ++i)
......
   57 |   FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
      |          ~~~~~~~~~~~~~~~~              
walk.cpp:57:3: note: in expansion of macro 'FOR'
   57 |   FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
      |   ^~~
walk.cpp:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(j, i, n) for(int i = j; i < n; ++i)
......
   63 |   FOR(1, j, dot[i].size())
      |          ~~~~~~~~~~~~~~~~              
walk.cpp:63:3: note: in expansion of macro 'FOR'
   63 |   FOR(1, j, dot[i].size())
      |   ^~~
#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...