Submission #893188

#	Time	Username	Problem	Language	Result	Execution time	Memory
893188		vjudge1	Ancient Books (IOI17_books)	C++17	0 / 100	1 ms	600 KiB

books

#include "books.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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);
    function<int(int)> dfs = [&](int u) {
        viz[u] = 1;
        int re = 0;
        for(auto it : L[u]) 
            if(!viz[it] && !alb[it]) {
                re += dfs(it);
            }
        for(auto it : L[u]) 
            if(!viz[it] && alb[it]) {
                if(dfs(it)) {
                    ++rec;
                    ++re;
                }
            }
        return !!re;
    };
    //cout << "rec e " << rec << "\n";
    dfs(0);
	return re + 2 * (rec - 1);
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30