| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
my code, 454ms..求解trie节点数上限怎么确定欬~#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator