pku2827.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <map>
#include <string.h>
#define size 20010
#define ONLINE
#ifndef ONLINE
#include <time.h>
#endif

using namespace std;

typedef map<int, int> MapIndex;

typedef struct
{
	int hd;
	int ds;
}Node;

Node nd[size];
MapIndex m;
MapIndex::iterator pos;

int GetID(int x)
{
	int root;
	if (nd[x].hd == 0)
	{
		return x;
	}
	root = GetID(nd[x].hd);
	nd[x].ds += nd[nd[x].hd].ds;
	nd[x].hd = root;
	return root;
}

int main()
{

#ifndef ONLINE
	freopen("2827.in", "r", stdin);
	clock_t start = clock();
#endif
	
	int M;
	int i;
	int s, e, d, hs, he, cnt, ps, pe, tmp;
	while (EOF != scanf("%d", &M) && M)
	{
		m.clear();
		memset(nd, 0, sizeof(nd));
		cnt = 1;
		for (i = 0; i < M; i++)
		{
			scanf("%d %d %d", &s, &e, &d);
			if (s > e)
			{
				tmp = s;
				s = e;
				e = tmp;
			}
			s--;
			pos = m.find(s);
			if (pos == m.end())
			{
				m[s] = cnt++;
			}
			ps = m[s];
			pos = m.find(e);
			if (pos == m.end())
			{
				m[e] = cnt++;
			}
			pe = m[e];
			hs = GetID(ps);
			he = GetID(pe);
			if (hs != he)
			{
				printf("Accept\n");
				nd[he].hd = hs;
				nd[he].ds = d + nd[ps].ds - nd[pe].ds;
			}
			else
			{
				if (nd[pe].ds - nd[ps].ds == d)
				{
					printf("Accept\n");
				}
				else
				{
					printf("Bug Detected %d\n", nd[pe].ds - nd[ps].ds);
				}
			}
		}
	}
#ifndef ONLINE
	printf("TIME:%dms\n", clock() - start);
#endif
	return 0;
}