| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1080188 | TB_ | Ancient Books (IOI17_books) | C++17 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define F first
#define S second
#define pb push_back
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
typedef vector<ll> vl;
typedef vector<vl> vvl;
struct UnionFind{
vl p, siz;
ll n;
UnionFind(int n) : n(n){
p.assign(n, 1);
siz.assign(n, 1);
fo(i, n) p[i] = i;
}
int find(int x){
if(x == p[x]) return x;
return p[x] = find(p[x]);
}
bool same(int a, int b){
return find(a) == find(b);
}
void unite(int a, int b){
a = find(a);
b = find(b);
if(a == b) return;
if(siz[b] > siz[a]) swap(a, b);
siz[a]+=siz[b];
p[b] = a;
}
};
vl color, nextB;
ll ans = 0, c = 0;
void dfs(int u){
if(color[u]!=-1) return;
color[u] = c;
dfs(nextB[u]);
ans+=abs(nextB[u]-u);
}
long long minimum_walk(std::vector<int> p, int s){
ll n = p.size();
fo(i, n)nextB.pb(p[i]);
color.assign(n, -1);
fo(i, n){
if((nextB[i] == i && i)|| color[i]!=-1) continue;
dfs(i);
c++;
}
priority_queue<tuple<ll, ll, ll>> pq;
fo(i, n){
if(color[i]==-1) continue;
fo(j, n){
if(color[j]==-1) continue;
pq.push({-abs(j-i), color[i], color[j]});
}
}
UnionFind uf(c);
ll cost, from, to;
while(!pq.empty()){
tie(cost, from, to) = pq.top();
pq.pop();
if(uf.same(from, to)) continue;
uf.unite(from, to);
ans-=cost*2;
}
return ans;
}
int main(){
vector<int> a = {2, 1, 0, 3};
ll res = minimum_walk(a, 0);
deb(res);
return 0;
}