oj.uz

Submission #149025

# Submission time Handle Problem Language Result Execution time Memory
149025 2019-09-01T05:35:38 Z 이 대회 미분 되나요?(#3668, wookje, edenooo, jms100300) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 2793 ms 38940 KB 
#include "island.h"
#include<assert.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;

//https://github.com/rlaguilar/Programming-Contests/blob/master/data-structures/persistent%20array.cpp
/*  <persistent array>  */
const int MAXN = 101010, MAXQ = 360360, MAXS = 50000000;
int lch[MAXS], rch[MAXS], cnt;

int new_node(int l, int r)
{
	assert(cnt < MAXS);
	lch[cnt] = l;
	rch[cnt] = r;
	return cnt++;
}

struct p_array
{
	int n, root;

	int build(int *a, int n)
	{
		if (n == 1)
			return new_node(*a, *a);

		int m = n / 2;
		return new_node(build(a, m), build(a + m, n - m));
	}

	p_array(int *a, int n) : n(n)
	{
		root = build(a, n);
	}

	p_array(int n = 0, int root = 0) : n(n), root(root)
	{}

	int get(int v, int n, int i)
	{
		if (n == 1)
			return lch[v];

		int m = n / 2;

		return i < m ? get(lch[v], m, i) : get(rch[v], n - m, i - m);
	}

	// get the value at potition i.
	int operator [] (int i)
	{
		return get(root, n, i);
	}

	int set(int v, int n, int i, int x)
	{
		if (i < 0 || i >= n)
			return v;

		if (n == 1)
			return new_node(x, x);

		int m = n / 2;
		return new_node(set(lch[v], m, i, x), set(rch[v], n - m, i - m, x));
	}

	// get the resultant array of setting value x to position i.
	p_array set(int i, int x)
	{
		return p_array(n, set(root, n, i, x));
	}
}root[MAXQ];    // root[v] = root of the tree that represent the version # v of the array.

/*  </persistent array>    */

int v, Data[MAXN];
char c;

int find_set(p_array &Data, int a)
{
	int p = Data[a];

	if (p < 0)
		return a;

	int ans = find_set(Data, p);
	//Data = Data.set(a, ans);
	return ans;
}

p_array union_set(p_array &Data, int a, int b)
{
	a = find_set(Data, a);
	b = find_set(Data, b);

	if (a != b)
	{
		int cnt_a = Data[a], cnt_b = Data[b];

		if (cnt_a > cnt_b)
			swap(a, b);

		p_array ans = Data.set(a, cnt_a + cnt_b);
		ans = ans.set(b, a);
		return ans;
	}
	else
		return Data;
}

int N, M;

void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	N = F.size(), M = S.size();

	memset(Data, -1, sizeof Data);
	root[M] = p_array(Data, N + 1);
	for (int i = M - 1; i >= 0; i--)
		root[i] = union_set(root[i + 1], F[S[i]], F[E[i]]);
}

int Separate(int A, int B){

	int lo = 0, hi = M;
	for (int i = 0; i < 20; i++)
	{
		int mid = lo + hi >> 1;
		if (find_set(root[mid], A) == find_set(root[mid], B))
			lo = mid;
		else
			hi = mid;
	}
	return hi;
}

Compilation message

island.cpp: In function 'int Separate(int, int)':
island.cpp:130:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = lo + hi >> 1;
             ~~~^~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2438 ms 38932 KB Output is correct
2 Correct 2428 ms 38884 KB Output is correct
3 Correct 1869 ms 38652 KB Output is correct
4 Correct 2091 ms 38572 KB Output is correct
5 Correct 2197 ms 38880 KB Output is correct
6 Correct 2419 ms 38940 KB Output is correct
7 Correct 2241 ms 38920 KB Output is correct
8 Correct 2099 ms 38916 KB Output is correct
9 Correct 2752 ms 38616 KB Output is correct
10 Correct 2793 ms 38880 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3584 KB Output isn't correct
2 Halted 0 ms 0 KB -