Cod sursa(job #82836)

Utilizator MariusMarius Stroe Marius Data 9 septembrie 2007 13:43:28
Problema Count Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 kb
#include <stdio.h>

const char iname[] = "count.in";
const char oname[] = "count.out";

#define MAXN       30007
#define BUF_SIZE   800000
#define MAXGLBMEM  13000000

char buf[BUF_SIZE], *ptr_buf;

const int byte[8] = {1, 2, 4, 8, 16, 32, 64, 128};

unsigned char *G[MAXN][64];

unsigned char globalMemory[MAXGLBMEM];

int globalMemoryPointer;

int bit_count[32];


int *L[MAXN];

int n_nodes;

int max_clq, clq_cnt;

int queue[MAXN], in_queue[MAXN], degree[MAXN], tdegree[MAXN], deleted[MAXN], head, tail;


inline void add_edge(unsigned char *G[], const int y)
{
	if (G[y >> 9] == 0) {
		G[y >> 9] = (unsigned char *)(globalMemory + globalMemoryPointer);
		globalMemoryPointer += 64;
	}
	G[y >> 9][(y >> 3) & 63] |= 1 << (y & 7);
}

inline int query_edge(unsigned char *G[], const int y)
{
	if (G[y >> 9] == 0)
		return 0;
	return (G[y >> 9][(y >> 3) & 63] & (1 << (y & 7))) ? 1 : 0;
}

int get(void)
{
	int n = 0;

	for (; *ptr_buf < '0'; ++ ptr_buf) ;
	for (; '0' <= *ptr_buf; ++ ptr_buf)
		n = n * 10 + *ptr_buf - '0';
	return n;
}

void solve(const int x)
{
	int neigh[5], n_neigh = 0;
	int y;
	int KGraph;
	
	for (int i = degree[x] - 1; i >= 0; -- i) {
		y = L[x][i];
		if (deleted[y] == false)
			neigh[n_neigh ++] = y;
	}
	
	for (int stp = 1; stp < 1 << n_neigh; ++ stp) {
        if (bit_count[stp] > 3) 
			continue ;
		KGraph = true;
		for (int i = 0; i < n_neigh; ++ i) if (stp & (1 << i)) {
			for (int j = i + 1; j < n_neigh; ++ j) if (stp & (1 << j)) {
				if (query_edge(G[neigh[i]], neigh[j]) == 0)
					KGraph = false;
			}
		}
		if (KGraph) {
			if (max_clq < bit_count[stp] + 1)
				max_clq = bit_count[stp] + 1, clq_cnt = 1;
			else if (max_clq == bit_count[stp] + 1)
				clq_cnt ++;
		}
	}
}

void delete_it(const int x)
{
	int y;

	for (int i = degree[x] - 1; i >= 0; -- i) {
		y = L[x][i];
		if (in_queue[y] == false) {
			if ((-- tdegree[y]) < 6)
				queue[tail ++] = y, in_queue[y] = true;
		}
	}
	deleted[x] = true;
}

int main(void)
{
	int n_edges;
	int x, y;

	FILE *fi = fopen(iname, "r");

	buf[ fread(buf, 1, sizeof(buf), fi)] = 0;
	fclose(fi);

	ptr_buf = buf;
	n_nodes = get();
	n_edges = get();
	for (int i = 0; i < n_edges; ++ i) {
		x = get(), y = get();
		add_edge(G[x], y);
		add_edge(G[y], x);
		degree[x] ++, degree[y] ++;
	}
	for (int i = 1; i <= n_nodes; ++ i)
		L[i] = new int[degree[i]], tdegree[i] = degree[i], degree[i] = 0;

	ptr_buf = buf;
	n_nodes = get();
	n_edges = get();
	for (int i = 0; i < n_edges; ++ i) {
		x = get(), y = get();
		L[x][degree[x] ++] = y;
		L[y][degree[y] ++] = x;
	}

	for (int stp = 1; stp < 32; ++ stp) {
		for (int i = 0; i < 5; ++ i) if (stp & (1 << i))
			bit_count[stp] ++;
	}

	for (int i = 1; i <= n_nodes; ++ i) {
		if (tdegree[i] < 6)
			queue[tail ++] = i, in_queue[i] = true;
	}
	for (; head < tail; ++ head) {
		x = queue[head];
		solve(x);
		delete_it(x);
	}
	
	FILE *fo = fopen(oname, "w");

	fprintf(fo, "%d %d\n", max_clq, clq_cnt);
	fclose(fo);

	return 0;
}