Submission #1061141

#TimeUsernameProblemLanguageResultExecution timeMemory
1061141onbertAncient Books (IOI17_books)C++17
22 / 100
1038 ms1048576 KiB
#include "books.h" #include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 1e6 + 5, INF = 1e9; int p[maxn]; int vis[maxn]; bool taken[maxn]; int minimum_walk(vector<int32_t> P, int32_t s) { int n = P.size(); for (int i=0;i<n;i++) p[i] = P[i]; for (int i=0;i<n;i++) vis[i] = false; int ans = 0, cnt = 0; vector<pair<int,int>> vec = {{-1, -1}}; for (int i=0;i<n;i++) if (!vis[i]) { if (p[i]==i && i==s) { cnt++; vis[i] = cnt; vec.push_back({s, s}); } if (p[i]==i) continue; int u = i; pair<int,int> val = {u, u}; cnt++; while (true) { vis[u] = cnt; val.first = min(u, val.first); val.second = max(u, val.second); int v = p[u]; ans += abs(v-u); if (v==i) break; u = v; } vec.push_back(val); } if (vec.size()==1) return ans; sort(vec.begin(), vec.end()); int lastl = vec[1].first, mx = vec[1].second; int LL = -1, RR = -1; for (int i=2;i<vec.size();i++) { if (vec[i].first > mx) { if (lastl<=s && s<=mx) { LL = lastl, RR = mx; } lastl = vec[i].first; ans += (vec[i].first - mx)*2; } mx = max(vec[i].second, mx); } if (LL==-1) { LL = lastl, RR = mx; } // cout << LL << " " << RR << endl; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, vis[s]}); int dist[cnt+5]; for (int i=1;i<=cnt;i++) dist[i] = -1; while (pq.size() > 0) { int u = pq.top().second, d = pq.top().first; pq.pop(); if (vec[u].second < LL || vec[u].first > RR) dist[u] = -2; if (dist[u]!=-1) continue; dist[u] = d; for (int i=vec[u].first; i<=vec[u].second;i++) { if (dist[vis[i]]==-1) pq.push({d, vis[i]}); } for (int i=vec[u].first-1;i>=LL;i--) { if (p[i]!=i) { if (dist[vis[i]]==-1) pq.push({d + (vec[u].first - i)*2, vis[i]}); } } for (int i=vec[u].second+1;i<=RR;i++) { if (p[i]!=i) { if (dist[vis[i]]==-1) pq.push({d + (i - vec[u].first)*2, vis[i]}); } } } int MX = 0; for (int i=1;i<=cnt;i++) if (dist[i]!=-1) MX = max(dist[i], MX); ans += MX; return ans; }

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int32_t)':
books.cpp:43:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=2;i<vec.size();i++) {
      |                  ~^~~~~~~~~~~
#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...