Submission 1457 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
1457	30/05/2013 20:13:13	rlac	B - Conjuntos disjuntos	Accepted	94	10.3 KiB	GNU G++ 5.1.0

Code

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

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

using namespace std;

const int MAXN = 1e5 + 5;
int n, k, v, a[MAXN], b[MAXN], ans[MAXN], *addr[2 * MAXN], sp, value[2 * MAXN], data[MAXN];
char c[MAXN];
//vector<int> quest[MAXN], res[MAXN];

void set_value (int *ad, int val)
{	
	assert(sp < 2 * MAXN);
	value[sp] = *ad;
	addr[sp++] = ad;
	*ad = val;
}

void rollback (int tsp)
{
	for (; sp > tsp; --sp)
		*addr[sp - 1] = value[sp - 1];
}

int find_set (int a)
{
	while (data[a] >= 0)
		a = data[a];
		
	return a;
}

void union_set (int a, int b)
{
	a = find_set(a);
	b = find_set(b);
	
	if (a != b)
	{
		if (data[a] > data[b])
			swap(a, b);
			
		set_value(data + a, data[a] + data[b]);
		set_value(data + b, a);		
	}
}

const int MAXS = 2 * MAXN;
int VQ[MAXN], VR[MAXN], E[MAXS], next[MAXS], sz;

void add_edge(int V[], int u, int v)
{
	next[sz] = V[u]; E[sz] = v; V[u] = sz++;
}

void dfs (int u)
{	
	//for (int i = 0; i < quest[u].size(); ++i)
	for (int i = VQ[u]; i >= 0; i = next[i])
	{
		int idx = E[i];
		//int idx = quest[u][i];
		ans[idx] = find_set(a[idx]) == find_set(b[idx]);
	}
	
	int curr = sp;
	
	//for (int i = 0; i < res[u].size(); ++i)
	for (int i = VR[u]; i >= 0; i = next[i])
	{
		int idx = E[i];
		//int idx = res[u][i];
		union_set(a[idx], b[idx]);
		dfs(idx);
		rollback(curr);
	}
}

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);
		int TIME = clock();
	#endif
	//Add your code here...
	memset(data, -1, sizeof data);
	memset(VQ, -1, sizeof VQ);
	memset(VR, -1, sizeof VR);
	cin >> n >> k;
	
	for (int i = 1; i <= k; ++i)
	{
		cin >> c[i] >> v >> a[i] >> b[i];
		
		if (c[i] == '?')
		{
			//quest[v].push_back(i);
			add_edge(VQ, v, i);
		}
		else
		{
			//res[v].push_back(i);
			add_edge(VR, v, i);
		}
	}
	
	dfs(0);
	
	for (int i = 1; i <= k; ++i)
	{
		if (c[i] == '?')
			cout << (ans[i] ? "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.011 0.000 2612K ok
Test 02: 0.011 0.000 2668K ok
Test 03: 0.028 0.016 3072K ok
Test 04: 0.112 0.078 7012K ok
Test 05: 0.122 0.078 7148K ok
Test 06: 0.145 0.062 7800K ok
Test 07: 0.131 0.078 4660K ok
Test 08: 0.125 0.078 6216K ok
Test 09: 0.129 0.047 7484K ok
Test 10: 0.126 0.078 6216K ok
Test 11: 0.131 0.094 7584K ok
Test 12: 0.173 0.016 10512K ok
Test 13: 0.115 0.047 10516K ok
Accepted

Matcom Online Grader