Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

my code, 454ms..求解trie节点数上限怎么确定欬~

Posted by qddpx at 2012-07-25 23:44:44 on Problem 2513
#include <cstdio>
#include <cstring>
#define MAX (255000*2 + 5)

struct Node{
	int id;
	int hit[26];
	Node() {id = 0;}
}trie[MAX];

int uf[MAX];
int find(int x) {while(uf[x] >= 0) x=uf[x]; return x;}
void unin(int x, int y) {if((x=find(x)) != (y=find(y))) uf[y] = x;}
void ufinit() {memset(uf, -1, sizeof(uf));}

int ttr, ctr, deg[MAX];

int insert(char* s){
	int c;
	Node* node = &trie[0];
	while(c = *s++){
		if(!node->hit[c-'a'])
			node->hit[c-'a'] = ttr++;
		node = &trie[node->hit[c-'a']];
	}
	if(!node->id)
		node->id = ctr++;
	deg[node->id] ++;
	return node->id;
}

int main(){
	freopen("input.txt", "r", stdin);
	char a[11], b[11];
	int aid, bid, odd, suc;
	odd = 0;
	suc = ctr = ttr = 1;
	ufinit();
	while(scanf("%s%s", a, b) != EOF){
		aid = insert(a);
		bid = insert(b);
		unin(aid, bid);
	}
	aid = find(1);
	while(--ctr > 0 && suc){
		if(find(ctr) != aid)
			suc = 0;
		if(deg[ctr] % 2)
			odd ++;
		if(odd > 2)
			suc = 0;
	}
	if(suc)
		printf("Possible\n");
	else
		printf("Impossible\n");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator