Submission #49209

#	Time	Username	Problem	Language	Result	Execution time	Memory
49209		MatheusLealV	Ancient Books (IOI17_books)	C++17	0 / 100	3 ms	812 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
typedef long long ll;

int G[N], ok[N], cor, sz[N], C[N];

void dfs(int x)
{
	if(ok[G[x]]) return;

	ok[G[x]] = 1;

	dfs(G[x]);
}

void co(int x)
{
	if(C[G[x]]) return;

	C[G[x]] = cor, sz[cor] ++;

	co(G[x]);
}

ll minimum_walk(vector<int> p, int s)
{
	ll ans = 0;

	for(int i = 0; i < p.size(); i++) G[i] = p[i], ans += abs(i - p[i]);

	for(int i = 0; i < p.size(); i++)
	{
		if(C[i]) continue;

		++cor;

		C[i] = cor;

		sz[cor] = 1;

		co(i);
	}

	while(s >= 0)
	{
		dfs(s);

		int prox = -1, d = 2000000000;

		for(int i = 0; i < p.size(); i++)
		{
			if(ok[i] || sz[C[i]] <= 1) continue;

			if(abs(s - i) < d)
			{
				d = abs(s - i);

				prox = i;
			}
		}

		if(prox == -1) ans += s;

		else ans += d;

		s = prox;
	}

	return ans;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < p.size(); i++) G[i] = p[i], ans += abs(i - p[i]);
                 ~~^~~~~~~~~~
books.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < p.size(); i++)
                 ~~^~~~~~~~~~
books.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < p.size(); i++)
                  ~~^~~~~~~~~~

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