oj.uz

Submission #49209

# Submission time Handle Problem Language Result Execution time Memory
49209 2018-05-23T19:07:59 Z MatheusLealV Ancient Books (IOI17_books) C++17
0 / 100
 3 ms 812 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Incorrect 3 ms 812 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Incorrect 3 ms 812 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Incorrect 3 ms 812 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 812 KB 3rd lines differ - on the 1st token, expected: '3304', found: '5157'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Incorrect 3 ms 812 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -