#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
struct UF {
vi e;
UF(int N) : e(N, -1) {}
int repr(int u) {
while(e[u] >= 0) u = e[u];
return u;
}
int join(int u, int v) {
u = repr(u);
v = repr(v);
if(u == v) return 0;
if(e[u] >= e[v]) swap(u, v);
e[u] += e[v];
e[v] = u;
return 1;
}
};
long long minimum_walk(vi p, int s) {
int n = p.size();
vi ip(n);
for(int i = 0; i < n; ++i)
ip[p[i]] = i;
int re = 0, nrcic = 0;
vi vis(n, 0), cul(n, 0), alb(n, 0);
for(int i = 0; i < n; ++i) {
if(!vis[i]) {
int u = i;
while(!vis[u]) {
vis[u] = 1;
cul[u] = nrcic;
u = p[u];
}
alb[nrcic] = (i == p[i]);
nrcic++;
}
}
// cout << "alb: ";
// for(auto it : alb) cout << it << " ";
// cout << "\n";
vector<vi> L(nrcic);
for(int i = 0; i + 1 < n; ++i) {
if(cul[i] != cul[i + 1]) {
L[cul[i]].push_back(cul[i + 1]);
L[cul[i + 1]].push_back(cul[i]);
}
}
for(int i = 0; i < nrcic; ++i) {
sort(L[i].begin(), L[i].end());
L[i].resize(unique(L[i].begin(), L[i].end()) - L[i].begin());
}
for(int i = 0; i < n; ++i)
re += abs(i - p[i]);
int rec = alb[cul[s]];
for(int i = 0; i < nrcic; ++i)
rec += !alb[i];
vi viz(nrcic, 0);
alb[cul[s]] = 0;
function<void(int, vi&, int&nr)> dfs0 = [&](int u, vi& V, int &nr) {
viz[u] = 1;
++nr;
for(auto it : L[u]) {
if(!viz[it]) {
if(alb[it]) {
dfs0(it, V, nr);
} else {
V.push_back(it);
}
}
}
};
vector<pair<int, ii> > E;
for(int i = 0; i < nrcic; ++i) {
if(alb[i] && !viz[i]) {
vi vecini;
int w = 0;
dfs0(i, vecini, w);
if(vecini.size() == 2) {
int u = vecini[0], v = vecini[1];
E.push_back({w, ii{u, v}});
}
}
}
for(int i = 0; i < nrcic; ++i) {
for(auto it : L[i])
if(!alb[i] && !alb[it])
E.push_back({0, ii{i, it}});
}
sort(E.begin(), E.end());
UF Sol(nrcic);
for(auto [w, muchie] : E) {
auto [u, v] = muchie;
if(Sol.join(u, v)) {
rec += w;
}
}
// cout << "rec e " << rec << "\n";
return re + 2 * (rec - 1);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
500 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Incorrect |
1 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
500 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Incorrect |
1 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
500 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Incorrect |
1 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '4074' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
500 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Incorrect |
1 ms |
344 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
7 |
Halted |
0 ms |
0 KB |
- |