Submission #293005

#	Time	Username	Problem	Language	Result	Execution time	Memory
293005		Kastanda	Ancient Books (IOI17_books)	C++11	50 / 100	724 ms	85388 KiB

books

// M
#include<bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
const int N = 1000006;
int n, st, k, T[N], P[N], A[N], mn[N], mx[N];
vector < tuple < int , int , int > > E;
int Find(int v)
{
        return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
        v = Find(v);
        u = Find(u);
        if (v == u)
                return ;
        P[u] = v;
        mn[v] = min(mn[v], mn[u]);
        mx[v] = max(mx[v], mx[u]);
}
inline void AddEdge(int v, int u, int w)
{
        E.push_back({w, v, u});
}

long long minimum_walk(vector < int > _A, int _st)
{
        n = (int)_A.size();
        st = _st + 1;
        for (int i = 1; i <= n; i ++)
                A[i] = _A[i - 1] + 1;

        ll SM = 0, tot = 0;
        for (int i = 1; i <= n; i ++)
                SM += abs(A[i] - i);
        memset(P, -1, sizeof(P));
        for (int i = 1; i <= n; i ++)
                mn[i] = mx[i] = i;
        set < int > ST;
        for (int i = 1; i <= n; i ++)
                ST.insert(i);

        vector < int > M(n + 1, 0);
        vector < pair < int , int > > Roller;
        for (int i = 1; i <= n; i ++)
                if (!M[i] && A[i] != i)
                {
                        auto Do = [&](int l, int r){
                                if (l >= r)
                                        return ;
                                auto it = ST.lower_bound(l);
                                while (it != ST.end() && * it < r)
                                        Merge(* it, (* it) + 1), it = ST.erase(it);
                                return ;
                        };

                        vector < int > V;
                        int nw = i;
                        while (!M[nw])
                                V.push_back(nw), M[nw] = 1, nw = A[nw];
                        sort(V.begin(), V.end());
                        int is = 0;
                        for (int j : V)
                                if (j == st)
                                        is = 1;
                        for (int j = 0; j + 1 < (int)V.size(); j ++)
                        {
                                if (V[j + 1] < st || V[j] > st || is)
                                        Do(V[j], V[j + 1]);
                                else
                                        Roller.push_back({V[j], V[j + 1]});
                        }
                }

        /*
        for (int i = 1; i <= n; i ++)
                if (i != A[i])
                {
                                        int l = min(i, A[i]);
                        int r = max(i, A[i]);

                        Do(l, min(r, st - 1));
                        Do(max(st + 1, l), r);
                }
        */
        vector < pair < pair < int , int > , int > > vec;
        for (int i = 1; i <= n; i ++)
                if ((Find(i) == i && i != A[i]))
                        T[i] = ++ k, vec.push_back({{mn[i], mx[i]}, T[i]});
        if (Find(st) == st && A[st] == st)
        {
                T[st] = ++ k;
                vec.push_back({{st, st}, T[st]});
        }
        sort(vec.begin(), vec.end());


        //for (auto X : vec)
        //      printf("%d , %d :: %d\n", X.first.first, X.first.second, X.second);

        //assert(Find(st) == st);
        /*for (int i = 1; i <= n; i ++)
                if (i != A[i])
                {
                        int l = min(i, A[i]);
                        int r = max(i, A[i]);

                        if (l <= st && st <= r)
                                AddEdge(T[Find(l)], T[Find(r)], 0);
                }*/

        for (auto X : Roller)
        {
                int v = Find(X.first);
                int u = Find(X.second);
                AddEdge(T[v], T[u], 0);
        }

        for (int i = 0; i + 1 < k; i ++)
                AddEdge(vec[i].second, vec[i + 1].second, vec[i + 1].first.first - vec[i].first.second);

        sort(E.begin(), E.end());
        memset(P, -1, sizeof(P));
        int cc = 0;
        for (auto X : E)
        {
                int w, v, u;
                tie(w, v, u) = X;
                v = Find(v);
                u = Find(u);
                if (v == u)
                        continue;
                tot += w * 2;
                Merge(v, u);
                cc ++;
        }
        assert(cc == k - 1);

        tot = tot + SM;
        return tot;

        /*while (vec.size() > 1 && vec[(int)vec.size() - 2].second >= st)
                tot += vec.back().first - vec[(int)vec.size() - 2].second, vec.pop_back();
        if (vec.size() && vec.back().first >= st)
                tot += vec.back().first - st, vec.pop_back();
        reverse(vec.begin(), vec.end());
        while (vec.size() > 1 && vec[(int)vec.size() - 2].first <= st)
                tot += vec[(int)vec.size() - 2].first - vec.back().second, vec.pop_back();
        if (vec.size() && vec.back().second <= st)
                tot += st - vec.back().second, vec.pop_back();
        if (vec.size())
        {
                assert(vec.size() == 1 && vec[0].first <= st && st <= vec[0].second);
                if (A[st] == st)
                {
                        int l = st;
                        while (l && A[l] == l)
                                l --;
                        assert(l >= vec[0].first);
                        int Best = st - l;
                        int r = st;
                        while (r <= n && A[r] == r)
                                r ++;
                        assert(r <= vec[0].second);
                        Best = min(Best, r - st);
                        tot += Best;
                }
        }

        tot = tot * 2 + SM;
        return tot;*/
}

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