Submission #295652

#TimeUsernameProblemLanguageResultExecution timeMemory
295652williamMBDKAncient Books (IOI17_books)C++14
12 / 100
1 ms384 KiB
#include<bits/stdc++.h> using namespace std; #include "books.h" #define int long long long long minimum_walk(std::vector<signed> p, signed s) { int N = p.size(); vector<int> nodes (N, -1); int c = 0; int sum = 0; for(int i = 0; i < N; i++){ if(nodes[i] == -1){ if(p[i] == i) continue; // cout << "new" <<endl; int j = p[i]; // cout << i << endl; sum += abs(i - p[i]); nodes[i] = c; while(j != i){ sum += abs(j - p[j]); //right? nodes[j] = c; // cout << j << endl; j = p[j]; } c++; } } // cout << "here" << " " << c << endl; if(c == 0) return 0; priority_queue<pair<int,int>> q; vector<vector<pair<int,int>>> adj (c); for(int i = 0; i < N; i++){ if(nodes[i] == -1) continue; while(!q.empty() && q.top().second == nodes[i]){ q.pop(); } if(!q.empty()){ auto nb = q.top(); q.pop(); adj[nb.second].push_back({nb.first < p[i] ? 0 : ((i - nb.first) * 2), nodes[i]}); adj[nodes[i]].push_back({nb.first > p[i] ? 0 : ((i - nb.first) * 2), nb.second}); } q.push({i,nodes[i]}); } priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; vector<bool> intree (c); intree[0] = 1; for(auto e : adj[0]) { pq.push(e); // cout << 0 << " " << e.second << " " << e.first << endl; } int tree = 0; // cout << c << endl; for(int i = 0; i < c - 1; i++){ while(intree[pq.top().second]) pq.pop(); auto t = pq.top(); pq.pop(); intree[t.second] = 1; tree += t.first; for(auto e : adj[t.second]){ // cout << t.second << " " << e.second << " " << e.first << endl; pq.push(e); } } // cout << "herer" << endl; int md = LLONG_MAX; for(int i = s; i < N; i++){ if(nodes[i] != -1){ md = i - s; break; } } for(int i = s; i >= 0; i--){ if(nodes[i] != -1){ md = min(md, s - i); break; } } // cout << 2 * md << " " << sum << " " << tree << endl; return md * 2 + sum + tree; }
#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...