Submission #782290

#	Time	Username	Problem	Language	Result	Execution time	Memory
782290		ikaurov	Ancient Books (IOI17_books)	C++14	12 / 100	5 ms	4308 KiB

books

// #include "books.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'

const int INF = 1e9;

long long minimum_walk(std::vector<int> p, int s) {
	int n = sz(p);
  ll ans = 0;
  for (int i = 0; i < n; i++){
    ans += abs(i - p[i]);
  }
  int mincycle = -1, maxcycle = -1;
  for (int i = 0; i < n; i++) if (i != p[i]){
    mincycle = i;
    break;
  }
  for (int i = n - 1; i >= 0; i--) if (i != p[i]){
    maxcycle = i;
    break;
  }
  if (mincycle == -1) return 0;
  for (int i = mincycle, mx = -1; i < n;){
    mx = max(mx, p[i]);
    if (mx <= i){
      int j = i + 1;
      while (j < n && j == p[j]) j++;
      if (j == n) break;
      ans += 2 * (j - i), i = j;
    }
    else i++;
  }
  if (s < mincycle) return ans + 2 * (mincycle - s);
  if (s > maxcycle) return ans + 2 * (s - maxcycle);
  vector<bool> cycleend(n);
  for (int i = 0, mx = -1; i < n; i++){
    mx = max(mx, p[i]);
    if (mx <= i) cycleend[i] = 1;
  }

  vector<int> cur, used(n), cid(n), minpos(n, INF), maxpos(n, -1);
  vector<int> minl(n, INF), maxr(n, -1);

  int id = 0;

  function<void(int)> dfs = [&] (int v){
    used[v] = 1, cid[v] = id;
    minpos[id] = min(minpos[id], v);
    maxpos[id] = max(maxpos[id], v);
    if (!used[p[v]]) dfs(p[v]);
  };

  for (int i = 0; i < n; i++){
    if (used[i]) continue;
    dfs(i);
    id++;
  }

  vector<vector<int>> g(id);

  for (int i = 0; i < id; i++){
    for (int j = minpos[id]; j <= maxpos[id]; j++){
      g[cid[j]].pb(i);
    }
  }

  function<void(int, int)> dfs1 = [&] (int v, int val){
    minl[v] = val;
    for (auto u : g[v]) if (minl[u] == INF) dfs1(u, val);
  };

  function<void(int, int)> dfs2 = [&] (int v, int val){
    maxr[v] = val;
    for (auto u : g[v]) if (maxr[u] == -1) dfs2(u, val);
  };

  vector<int> order(id);
  iota(all(order), 0);

  sort(all(order), [&] (int i, int j){
    return minpos[i] < minpos[j];
  });

  for (auto i : order){
    if (minl[i] == INF) dfs1(i, minpos[i]);
  }

  sort(all(order), [&] (int i, int j){
    return maxpos[i] > maxpos[j];
  });

  for (auto i : order){
    if (maxr[i] == -1) dfs2(i, maxpos[i]);
  }

  vector<vector<int>> dp(n, vector<int>(n, INF));

  dp[minl[cid[s]]][maxr[cid[s]]] = 0;

  ll ans1;

  for (int len = 1; len <= n; len++){
    for (int l = 0; l + len - 1 < n; l++){
      int r = l + len - 1;
      if (dp[l][r] == INF) continue;
      ans1 = dp[l][r];
      if (l > 0 && !cycleend[l - 1]){
        int newl = min(l, minl[cid[l - 1]]), newr = max(r, maxr[cid[l - 1]]);
        dp[newl][newr] = min(dp[newl][newr], dp[l][r] + 2);
      }
      if (!cycleend[r] && r < n - 1){
        int newl = min(l, minl[cid[r + 1]]), newr = max(r, maxr[cid[r + 1]]);
        dp[newl][newr] = min(dp[newl][newr], dp[l][r] + 2);
      }
    }
  }

  return ans + ans1;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:127:16: warning: 'ans1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |   return ans + ans1;
      |                ^~~~

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