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