Submission #1048886

#TimeUsernameProblemLanguageResultExecution timeMemory
1048886fuad27Sky Walking (IOI19_walk)C++17
Compilation error
0 ms0 KiB
#include "walk.h" #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); 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 st, int ed) { #define int long long int n = h.size(); int m = y.size(); vector<int> bl; vector<int> br(m); bl.resize(n); iota(bl.begin(),bl.end(), 0); iota(br.begin(),br.end(), 0); sort(bl.begin(), bl.end(), [&](int u, int v) -> bool { return h[u] > h[v]; }); sort(br.begin(), br.end(), [&](int u, int v) -> bool { return y[u] > y[v]; }); int p1 = 0; set<int> s; map<int,vector<int>> mp; map<int,vector<int>> coords; vector<vector<pair<int,long long>>> g; map<pair<int,int>, int> cmp; auto add = [&](int x, int y) -> int { if(cmp.find(pair<int,int>(x, y))!=cmp.end())return cmp[{x, y}]; cmp[{x,y}]=g.size(); coords[x].push_back(y); g.push_back({}); return cmp[{x,y}]; }; for(int i = 0;i<m;i++) { while(p1 < n and h[bl[p1]] >= y[br[i]]) { mp[x[bl[p1]]].push_back(bl[p1]); s.insert(x[bl[p1++]]); } int prev=-1; for(auto it = s.lower_bound(x[l[br[i]]]);it!=s.end();it++) { if((*it) > x[r[br[i]]])break; int at = (*it); // cout << y[br[i]] << " " << at << endl; if(coords[at].size()) coords[at].push_back(y[br[i]]); else coords[at].push_back(0); add(at, y[br[i]]); add(at, 0); if(prev!=-1) { g[add(prev, y[br[i]])].push_back({add(at, y[br[i]]), abs(at-prev)}); g[add(at, y[br[i]])].push_back({add(prev, y[br[i]]), abs(at-prev)}); } prev=at; } } for(auto &i:coords) { sort(i.second.begin(), i.second.end()); for(int j = 1;j<(int)(i.second).size();j++) { // cout << i.first << " " << i.second[j-1] << " " << i.second[j] << endl; // cout << i.first << " " << i.second[j-1] << " " << i.second[j] << endl; g[add(i.first, i.second[j-1])].push_back({add(i.first, i.second[j]), abs(i.second[j]-i.second[j-1])}); g[add(i.first, i.second[j])].push_back({add(i.first, i.second[j-1]), abs(i.second[j]-i.second[j-1])}); } } // cout << endl; priority_queue<pair<long long,int>> pq; pq.push(pair<long long, int>(0ll, add(x[st], 0))); vector<long long> dist(g.size(), (long long)2e18); dist[add(x[st], 0)] = 0; map<int, pair<int,int>> revs; for(auto i:cmp) { revs[i.second] = i.first; } vt<bool> vis(g.size()); while(pq.size()) { int at = pq.top().second; if(vis[at])return; vis[at]=1; // cout << revs[at].first << " " << revs[at].second << " " << dist[at] << endl; pq.pop(); for(auto [to, w]:g[at]){ if(dist[to] > dist[at] + w) { dist[to] = dist[at]+w; pq.push(pair<long long, int> (-dist[to], to)); } } } return dist[add(x[ed], 0)]; #undef int }

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:83:2: error: 'vt' was not declared in this scope; did you mean 'st'?
   83 |  vt<bool> vis(g.size());
      |  ^~
      |  st
walk.cpp:83:5: error: expected primary-expression before 'bool'
   83 |  vt<bool> vis(g.size());
      |     ^~~~
walk.cpp:86:6: error: 'vis' was not declared in this scope
   86 |   if(vis[at])return;
      |      ^~~
walk.cpp:86:14: error: return-statement with no value, in function returning 'long long int' [-fpermissive]
   86 |   if(vis[at])return;
      |              ^~~~~~
walk.cpp:87:3: error: 'vis' was not declared in this scope
   87 |   vis[at]=1;
      |   ^~~