This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "books.h"
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
using ll = long long;
bool seen[1000005];
vector<int> P;
vector<int> t;
ll dfs(int i)
{
if (seen[i])
return 0;
seen[i] = true;
t.push_back(i);
return abs(i - P[i]) + dfs(P[i]);
}
ll minimum_walk(vector<int> p, int s)
{
P = p;
ll sum = 0;
int n = p.size();
vector<pair<int, int>> q;
q.push_back({s, s});
for (int i = 0; i < n; i++)
{
if (seen[i] or i == p[i])
continue;
t.clear();
sum += dfs(i);
sort(t.begin(), t.end());
q.push_back({t.front(), t.back()});
}
sort(q.begin(), q.end());
int lt = -1;
for (auto [a, b] : q)
{
if (lt == -1)
{
lt = b;
}
if (a > lt)
{
sum += 2 * (a - lt);
lt = b;
}
else
{
lt = max(lt, b);
}
}
return sum;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |