#include "island.h"
#include<assert.h>
#include<vector>
#include<algorithm>
using namespace std;
//https://github.com/rlaguilar/Programming-Contests/blob/master/data-structures/persistent%20array.cpp
/* <persistent array> */
const int MAXN = 100101, MAXQ = 50505, 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[0] = p_array(Data, N + 1);
for (int i = M - 1; i >= 0; i--)
root[i] = union_set(root[(i + 1) % M], 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 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:118:2: error: 'memset' was not declared in this scope
memset(Data, -1, sizeof Data);
^~~~~~
island.cpp:118:2: note: suggested alternative: 'fd_set'
memset(Data, -1, sizeof Data);
^~~~~~
fd_set
island.cpp: In function 'int Separate(int, int)':
island.cpp:129:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = lo + hi >> 1;
~~~^~~~
