Submission 1456 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
1456	30/05/2013 19:56:34	rlac	B - Conjuntos disjuntos	Time Limit Exceeded	2012	10.8 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);		
	}
}

void dfs (int u)
{	
	for (int i = 0; i < quest[u].size(); ++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)
	{
		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);
	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);
		else
			res[v].push_back(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.014 0.016 4164K ok
Test 02: 0.017 0.016 4236K ok
Test 03: 0.146 0.125 4880K ok
Test 04: 2.197 2.012 11008K time limit exceeded

Matcom Online Grader