Submission #1207505

#TimeUsernameProblemLanguageResultExecution timeMemory
1207505HappyCapybaraSky Walking (IOI19_walk)C++17
0 / 100
234 ms28284 KiB
#include "walk.h" #include<bits/stdc++.h> using namespace std; #define ll long long ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int G){ int n = x.size(); int m = l.size(); vector<vector<pair<int,ll>>> g(m+2); vector<vector<int>> ev; for (int i=0; i<m; i++){ ev.push_back({l[i], 1, i}); ev.push_back({r[i], -1, i}); } set<int> hs; map<int,int> htw; sort(ev.begin(), ev.end()); int i = 0; //cout << "a" << endl; while (i < ev.size()){ //cout << i << endl; int ct = ev[i][0]; set<int> rm; while (i < ev.size() && ev[i][0] == ct && ev[i][1] == -1){ hs.erase(y[ev[i][2]]); rm.insert(ev[i][2]); i++; } while (i < ev.size() && ev[i][0] == ct && ev[i][1] == 1){ hs.insert(y[ev[i][2]]); htw[y[ev[i][2]]] = ev[i][2]; i++; } //cout << "b" << endl; for (int w : rm){ auto it = hs.upper_bound(y[w]); if (it != hs.end()) g[w].push_back({htw[*it], *it-y[w]}); if (it != hs.begin()) it--; if (1){ g[w].push_back({htw[*it], y[w]-*it}); if (*it == y[w]){ if (it != hs.begin()){ it--; g[w].push_back({htw[*it], y[w]-*it}); } } } } if (ct == 0 && !hs.empty()) g[m].push_back({htw[*hs.begin()], *hs.begin()}); if (ct == n-1){ for (int w : rm) g[w].push_back({m+1, y[w]}); } } /*for (int i=0; i<=m+1; i++){ cout << i << endl; for (pair<int,int> next : g[i]) cout << next.first << " " << next.second << endl; }*/ priority_queue<pair<ll,int>> pq; vector<bool> seen(m+2, false); pq.push({0, m}); //cout << "c" << endl; while (!pq.empty()){ ll d = -pq.top().first; int cur = pq.top().second; pq.pop(); if (seen[cur]) continue; seen[cur] = true; if (cur == m+1) return d+(ll)(x[n-1]-x[0]); for (pair<int,ll> next : g[cur]) pq.push({-(d+next.second), next.first}); } return -1; }
#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...