Source

Problem Id:1703  User Id:yangguo981 
Memory:484K  Time:609MS
Language:C++  Result:Wrong Answer

Source 

#include <numeric>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <algorithm>
#include <functional>
#include <iterator>
#include <cmath>
#include <iostream>
#include <sstream>
#include <fstream>
#include <list>
#include <bitset>
using namespace std;

typedef pair<int, int> PII;

#define BE(a) (a).begin(),(a).end()
#define FOR(i,j,k) for((i)=(j); (i)<(k); ++(i))
#define REP(i,n) FOR((i), 0, (n))
#define LENGTH(x) (sizeof((x))/sizeof(((x)[0])))

int T,N,M;
int parent[1000001];
//vector<int> parent;
PII getRoot(int x){
	int level = 0;
	while(parent[x] >= 0)
		x = parent[x],
		++level;
	return PII(x, level);
}
void merge(int x, int y){
	int r1 = getRoot(x).first;
	int r2 = getRoot(y).first;	
	if (r1 == r2) return;
	int level1 = getRoot(x).second;
	int level2 = getRoot(y).second;
	int count1 = parent[r1];
	int count2 = parent[r2];
	//x->y
	if (level1 > level2){
		int current = x,
		next = parent[current];
		while(next >= 0){
			int temp = parent[next];
			parent[next] = current;
			current = next;
			next = temp;
		}
		//parent[next] = current;
		parent[r2] += count1;
		parent[x] = y;
	}
	//y->x
	else{
		int current = y,
		next = parent[current];
		while(next >= 0){
			int temp = parent[next];
			parent[next] = current;
			current = next;
			next = temp;
		}
		//parent[next] = current;
		parent[r1] += count2;
		parent[y] = x;
	}
}
int main(){
	//ifstream cin("1.txt");
	cin >> T;
	while(T--){
		//cin >> N >> M;
		scanf("%d%d",&N,&M);
		char sign;
		int a,b,i;
		REP(i,N) parent[i] = -1;
		//parent.assign(N, -1);
		while(M--){
			//cin >> sign >> a >> b;
			cin >> sign;scanf("%d%d",&a,&b);
			if (sign == 'A'){
				PII p1 = getRoot(a);
				PII p2 = getRoot(b);
				if (p1.first != p2.first)
					printf("Not sure yet1.\n");
				else if (p1.second%2 == p2.second%2)
					printf("In the same g1ang.\n");
				else 
					printf("In differ2ent gangs.\n");
			}
			else merge(a, b);
		}
	}
	return 0;
}

• 吼吼，parent[i] = -1改成memset就过了。ft到死。。 (2439) yangguo981 2006-10-16 12:45:39