Cod sursa(job #215451)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 18 octombrie 2008 18:37:59
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define maxm 65536 * 2 + 4
#define maxn 4100

long v[maxm], next[maxm], first[maxn], t[maxm], list[maxn], nr[maxn], start[maxn], ok[maxn], i, n, m, a, b, last;

int cmp(const void *a, const void *b) {
	return *(long *)a - *(long *)b;
}

long calc(long a, long b) {
	long i, val = 0;
	long x = start[a], y = start[b];
	for (i = x; i < x + nr[a]; ++i) {
		if (t[i] > b) {
			++ok[t[i]];
		}
	}
	for (i = y; i < y + nr[b]; ++i) {
		if (t[i] > b) {
			if(ok[t[i]]) {
				++val;
			}
		}
	}
	for (i = x; i < x + nr[a]; ++i) {
		if(t[i] > b) {
			--ok[t[i]];
		}
	}
	return val;
}

int main() {
	freopen("triplete.in", "r", stdin);
	freopen("triplete.out", "w", stdout);
	scanf("%ld %ld", &n, &m);
	for (i = 1; i <= m; ++i) {
		scanf("%ld %ld", &a, &b);
		v[i * 2 - 1] = a;
		v[i * 2] = b;
		next[i * 2] = first[a];
		next[i * 2 - 1] = first[b];
		first[a] = i * 2;
		first[b] = i * 2 - 1;
	}
	for (i = 1; i <= n; ++i) {
		long poz = 0, x;
		memset(list, 0, sizeof(list));
		x = first[i];
		while (x) {
			list[++poz] = v[x];
			x = next[x];
		}
		qsort(list + 1, poz, sizeof(list[0]), cmp);
		start[i] = last + 1;
		nr[i] = poz;
		for (long ii = 1; ii <= poz; ++ii) {
			t[++last] = list[ii];
		}
	}
	long s = 0;
	for (i = 1; i <= n; ++i) {
		for (long j = start[i]; j < start[i] + nr[i]; ++j) {
			if (t[j] > i) {
				s += calc(i, t[j]);
			}
		}
	}
	printf("%ld\n", s);
	return 0;
}