Submission #1011614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011614		c2zi6	Ancient Books (IOI17_books)	C++14	42 / 100	2068 ms	55676 KiB

books

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "books.h"

namespace TEST1 {
    map<VI, int> ans = {
        {{2, 3, 0, 1}, 8},
        {{2, 3, 1, 0}, 8},
        {{3, 2, 0, 1}, 8},
        {{3, 2, 1, 0}, 8},
        {{1, 0}, 2},
        {{}, 0}
    };
    ll solve(VI p, int S) {
        while (p.size() && p.back() == p.size()-1) p.pop_back();
        if (ans.count(p)) return ans[p];
        if (p.size() == 4) return 6;
        if (p.size() == 3) return 4;
        return ans[p];
    }
};
namespace TEST2 {
    ll solve(VI p, int s) {
        int n = p.size();
        VI vis(n);
        int upto = 0;
        ll ans = 0;
        rep(u, n) if (!vis[u]) {
            int v = u;
            if (v == p[v]) {
                vis[v] = true;
                continue;
            }
            if (v > upto) ans += 2*(v-upto);
            do {
                vis[v] = true;
                setmax(upto, v);
                ans += abs(p[v]-v);
                v = p[v];
            } while (v != u);
        }
        return ans;
    }
};
namespace TEST4 {
    int s;
    VI p;
    VI vis, group;
    ll ans;
    map<PII, VI> comps;
    PII getcomp(int s) {
        PII ret{s, s};
        int u = s;
        VI vec;
        do {
            vec.pb(u);
            vis[u] = true;
            setmin(ret.ff, u);
            setmax(ret.ss, u);
            ans += abs(p[u]-u);
            u = p[u];
        } while (u != s);
        for (int u : vec) comps[ret].pb(u);
        return ret;
    }
    PII skizbp;
    void compressranges(VPI& ranges) {
        int n = ranges.size();
        VI vis(n);
        function<void(int)> dfs;
        VI comp;
        dfs = [&](int u) {
            comp.pb(u);
            vis[u] = true;
            rep(v, n) if (!vis[v]) {
                if (ranges[v].ss < ranges[u].ff || ranges[v].ff > ranges[u].ss) continue;
                if (ranges[u].ff < ranges[v].ff && ranges[v].ss < ranges[u].ss) continue;
                if (ranges[v].ff < ranges[u].ff && ranges[u].ss < ranges[v].ss) continue;
                dfs(v);
            }
        };
        if (true) {
            VPI tmp;
            rep(u, n) if (!vis[u]) {
                comp.clear();
                dfs(u);
                PII ret = {+2e9, -2e9};
                for (int u : comp) {
                    setmin(ret.ff, ranges[u].ff);
                    setmax(ret.ss, ranges[u].ss);
                }
                VI vec;
                for (int u : comp) {
                    for (int x : comps[ranges[u]]) {
                        vec.pb(x);
                    }
                }
                comps[ret].clear();
                for (int x : vec) comps[ret].pb(x);
                if (u == 0) skizbp = ret;
                tmp.pb(ret);
            }
            ranges = tmp;
        }
        sort(all(ranges));
        PII glxavor = {s, s};
        int cur = -1;
        VPI roots;
        while (true) {
            auto it = upper_bound(all(ranges), PII{cur, +2e9});
            if (it == ranges.end()) break;
            roots.pb(*it);
            if (it->ff <= s && s <= it->ss) {
                glxavor = *it;
            }
            cur = it->ss;
        }
        replr(i, 1, roots.size()-1) {
            ans += (roots[i].ff - roots[i-1].ss)*2;
        }

        VPI tmp{glxavor};
        for (PII p : ranges) {
            if (glxavor.ff < p.ff && p.ss < glxavor.ss) {
                tmp.pb(p);
            }
        }
        ranges = tmp;
    }
    ll solve(VI PARG, int SARG) {p = PARG, s = SARG;
        VPI ranges;
        vis = VI(p.size());
        group = VI(p.size(), -1);
        ranges.pb(getcomp(s));
        rep(u, p.size()) if (u != p[u] && !vis[u]) ranges.pb(getcomp(u));
        compressranges(ranges);
        sort(all(ranges), [&](PII a, PII b){
                    swap(a.ff, a.ss);
                    swap(b.ff, b.ss);
                    return a < b;
                });
        int n = ranges.size();
        VPI points;
        rep(i, n) {
            for (int x : comps[ranges[i]]) {
                points.pb({x, i});
            }
        }
        sort(all(points));
        VVPI gp(n);
        rep(u, n) {
            auto[l, r] = ranges[u];
            VPI::iterator(it);
            it = upper_bound(all(points), PII{r, +2e9});
            if (it != points.end()) {
                gp[u].pb({it->ss, (it->ff-r)*2});
            }
            it = lower_bound(all(points), PII{l, -2e9});
            if (it != points.begin()) {it--;
                gp[u].pb({it->ss, (l-it->ff)*2});
            }
        }

        int start = -1;
        rep(i, n) if (ranges[i] == skizbp) start = i;

        priority_queue<PLL> pq;
        VL dist(n, 1e18);
        VI vis(n);
        pq.push({0, start});
        dist[start] = 0;
        while (pq.size()) {
            int u = pq.top().ss;
            pq.pop();
            if (vis[u]) continue;
            vis[u] = true;
            for (auto[v, w] : gp[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({-dist[v], v});
                }
            }
        }

        return ans + dist.back();
    }
}


ll minimum_walk(VI p, int s) {
    return TEST4::solve(p, s);
    return TEST2::solve(p, s);
    if (p.size() <= 4) return TEST1::solve(p, s);
	return 0;
}

Compilation message (stderr)

books.cpp: In function 'll TEST1::solve(VI, int)':
books.cpp:44:37: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while (p.size() && p.back() == p.size()-1) p.pop_back();
      |                            ~~~~~~~~~^~~~~~~~~~~~~
books.cpp: In function 'll TEST4::solve(VI, int)':
books.cpp:181:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  181 |             auto[l, r] = ranges[u];
      |                 ^
books.cpp:182:26: warning: unnecessary parentheses in declaration of 'it' [-Wparentheses]
  182 |             VPI::iterator(it);
      |                          ^
books.cpp:206:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  206 |             for (auto[v, w] : gp[u]) {
      |                      ^

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