Submission 1455 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
1455	30/05/2013 19:53:27	rlac	B - Conjuntos disjuntos	Accepted	296	31.3 KiB	GNU G++ 5.1.0

Code

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>

#ifdef RLAC
	#define DEB(a)			cerr << __LINE__ << ": " << #a << " = " << (a) << endl
	#define OUT(a, n)		for (int J = 0; J < (n); ++J)	cerr << (a)[J] << " \n"[J == (n) - 1];
	#define NAME			"B"
#else
	#define DEB(a)
	#define OUT(a, n)
#endif

using namespace std;

/*	Begin persistent array	*/
const int MAXN = 1e5 + 5, MAXQ = MAXN, MAXS = 1e8;
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);
	}
	
	//Devuelve el valor del array en la posición 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));
	}
	
	//Assigna a la posición i del array el valor x.
	p_array set (int i, int x)
	{
		return p_array(n, set(root, n, i, x));
	}
}array[MAXQ];	//array[v] = array que representa la versión # v de la estructura.

/*	End persistent array	*/

int n, k, a, b, 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 main ()
{
	//Improvement region
	ios_base::sync_with_stdio(0);
	cin.tie(0);

//Input region
	#ifdef RLAC
		system("notepad "NAME".in");
		freopen(NAME".in", "r", stdin);
		FILE * FILE_NAME = freopen(NAME".out", "w", stdout);
		freopen(NAME".err", "w", stderr);
		int TIME = clock();
	#endif
	//Add your code here...
	cin >> n >> k;
	memset(data, -1, sizeof data);
	array[0] = p_array(data, n + 1);
	
	for (int i = 1; i <= k; ++i)
	{
		cin >> c >> v >> a >> b;
		
		if (c == '+')
			array[i] = union_set(array[v], a, b);
		else
		{			
			int id_b = find_set(array[v], b);
			int id_a = find_set(array[v], a);
			cout << ((id_a == id_b) ? "Si" : "No") << '\n';
		}	
	}	
	//Output region
	#ifdef RLAC
		cout << flush;
		clog << clock() - TIME << endl;
		fclose(FILE_NAME);
		system("notepad "NAME".out");
	#endif
	return 0;
}

Judgement Details

Test 01: 0.018 0.000 2600K ok
Test 02: 0.017 0.016 2624K ok
Test 03: 0.029 0.016 2800K ok
Test 04: 0.204 0.172 2804K ok
Test 05: 0.194 0.172 5032K ok
Test 06: 0.427 0.250 18096K ok
Test 07: 0.361 0.234 18016K ok
Test 08: 0.390 0.296 18096K ok
Test 09: 0.355 0.234 18068K ok
Test 10: 0.348 0.218 17964K ok
Test 11: 0.301 0.172 16576K ok
Test 12: 0.377 0.203 32084K ok
Test 13: 0.383 0.234 31860K ok
Accepted

Matcom Online Grader