Submission #149165

#	Time	Username	Problem	Language	Result	Execution time	Memory
149165		이 대회 미분 되나요? (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	31 / 100	2485 ms	38888 KiB

island

#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 Data[MAXN];

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 + 10);
	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 = -1, hi = M;
	for (int i = 0; i < 20; i++)
	{
		int mid = lo + hi >> 1;
		int aa = find_set(root[mid], A);
		int bb = find_set(root[mid], B);
		if (aa == bb)
			lo = mid;
		else
			hi = mid;
	}
	return hi;
}

Compilation message (stderr)

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

• Subtask 1: 31 / 31
• Subtask 2: 0 / 39
• Subtask 3: 0 / 30