oj.uz

Submission #137607

# Submission time Handle Problem Language Result Execution time Memory
137607 2019-07-28T07:25:57 Z Mahdi_Jfri Ancient Books (IOI17_books) C++14
0 / 100
 6 ms 4220 KB 
#include "books.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e6 + 20;

int par[maxn];

int root(int v)
{
	return par[v] < 0? v : par[v] = root(par[v]);
}

bool merge(int v , int u)
{
	v = root(v) , u = root(u);
	if(v == u)
		return 0;

	par[v] = u;
	return 1;
}

long long minimum_walk(vector<int> p, int s)
{
	memset(par , -1 , sizeof par);
	ll res = 0;
	int n = p.size();

	vector<int> val;
	for(int i = 0; i < n; i++)
	{
		res += abs(p[i] - i) , merge(i , p[i]);
		if(p[i] != i || i == s)
			val.pb(i);
	}

	int m = val.size();
	vector<pair<int , pair<int , int> > > tmp;
	for(int i = 0; i + 1 < m; i++)
		tmp.pb({val[i + 1] - val[i] , {val[i] , val[i + 1]}});
	sort(tmp.begin() , tmp.end());

	for(auto x : tmp)
	{
		int a = x.second.first , b = x.second.second;
		if(merge(a , b))
			res += 2 * x.first;
	}
	return res;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 4216 KB Output is correct
5 Correct 6 ms 4216 KB Output is correct
6 Incorrect 6 ms 4216 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 6 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 4216 KB Output is correct
5 Correct 6 ms 4216 KB Output is correct
6 Incorrect 6 ms 4216 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 6 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 4216 KB Output is correct
5 Correct 6 ms 4216 KB Output is correct
6 Incorrect 6 ms 4216 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 5 ms 4220 KB 3rd lines differ - on the 1st token, expected: '3304', found: '4074'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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