Submission #207586

#	Time	Username	Problem	Language	Result	Execution time	Memory
207586		AlexLuchianov	Ancient Books (IOI17_books)	C++14	0 / 100	5 ms	376 KiB

books

#include "books.h"
#include <cmath>
#include <iostream>
#include <cassert>
#include <vector>

using namespace std;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
using ll = long long;

int const nmax = 1000000;

namespace Dsu{
  std::vector<int> mult;
  void initialize(int n){
    mult.resize(1 + n);
    for(int i = 1;i <= n; i++)
      mult[i] = i;
  }
  int jump(int gala){
    if(mult[gala] != gala)
      mult[gala] = jump(mult[gala]);
    return mult[gala];
  }
  bool unite(int gala, int galb){
    gala = jump(gala);
    galb = jump(galb);
    if(gala == galb)
      return 0;
    mult[galb] = gala;
    return 1;
  }
}

int seen[1 + nmax];
int target[1 + nmax];

void processCycle(int node, ll &result){
  seen[node] = 1;
  result += fabs(target[node] - node);
  Dsu::unite(node, target[node]);
  if(seen[target[node]] == 0)
    processCycle(target[node], result);
}

struct Edge{
  int x, y;
  int cost;
  bool operator < (Edge const &a) const {
    return cost < a.cost;
  }
};

long long minimum_walk(std::vector<int> p, int start) {
  int n = p.size();
  for(int i = 0; i < n; i++)
    target[i] = p[i];
  Dsu::initialize(n);
  ll result = 0;
  for(int i = 0; i < n; i++)
    if(i != target[i] && seen[i] == 0)
      processCycle(i, result);
  int last = -1;

  vector<Edge> v;
  for(int i = 0; i < n; i++){
    if(i != target[i] || i == start) {
      if(0 <= last)
        v.push_back({Dsu::jump(last), Dsu::jump(i), i - last});
      last = i;
    }
  }

  for(int i = 0; i < v.size(); i++)
    if(Dsu::unite(v[i].x, v[i].y) == 1)
      result += 2 * v[i].cost;
	return result;
}

/*
5 1
3 0 2 1 4

6 2
5 1 2 3 4 0
*/

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++)
                  ~~^~~~~~~~~~

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