PKU 3513 Let's Go to the Movies
http://poj.org/problem?id=3513
1組以上の家族で映画に行く。
このとき、映画は一世帯分(親とその子供達)のチケットと一人分のチケットを使って見ることが出来る。
それぞれのチケットの値段が分かっているとき、全員が映画を見るために必要な最小の費用を求めろというような問題。
木DP的な問題。
時間厳し過ぎる問題だと思いました。
3秒くらいあってもいい気がします。
あと入力の形式が面倒くさいので、パースも大変面倒くさいことになりました。
ハッシュに書き換えたらTLEがWAになったのですが、その原因が分からなくてテストケースを取りに行こうと思いましたが、昨日テストケースを見てしまった問題があったので、それを反省して自分でランダムケースを書いたら小さいケースで原因が見つかってほっとしました。
あまりに汚すぎて誰も読まないであろうソースコード
typedef struct _node{ char*key; PI val; _node*next; }node; const int hashMod=3000000; node* hash[hashMod]; node ent[100000]; int sz; PI getval(char*key,int ch=0){ int ha=0; for(char*p=key;*p;++p)ha=(ha*67+*p)%hashMod; for(node*p=hash[ha];p;p=p->next) if(strcmp(p->key,key)==0){ p->val.S|=ch; return p->val; } node*p=hash[ha]; hash[ha]=ent+sz; hash[ha]->key=key; hash[ha]->next=p; return hash[ha]->val=mp(sz++,ch); } int sing,fami; vector<int> vec[100000]; pair<PI,PI> dfs(int num){ PI nt(0,0); PI sti(sing,1),fti(fami,1); rep(i,SZ(vec[num])){ pair<PI,PI> st=dfs(vec[num][i]); nt.F+=st.F.F; nt.S+=st.F.S; sti.F+=st.F.F; sti.S+=st.F.S; fti.F+=min(st.F,st.S).F; fti.S+=min(st.F,st.S).S; } return mp(min(sti,fti),nt); } char input[1000000]; char*pos; int getnum(){ while(!isdigit(*pos))++pos; int ret=*pos++&15; while(isdigit(*pos))ret=(ret<<3)+(ret<<1)+(*pos++&15); return ret; } char* getli(){ while(isspace(*pos))++pos; char* ret=pos; while(*pos!='\n' && *pos!='\r')++pos; *pos=0; return ret; } char* getstr(char*&it){ while(!isalpha(*it))++it; char*ret=it; while(isalpha(*it))++it; *it=0; return ret; } void go(){ while(isspace(*pos))++pos; } main(){ fread(input,sizeof(input),1,stdin); pos=input; int k=0; while(true){ go(); sing=getnum(); go(); fami=getnum(); if(!sing && !fami)break; memset(hash,0,sizeof(hash)); sz=0; while(true){ go(); if(isdigit(*pos))break; char*li=getli(); char* par=getstr(li); int bsz=sz; PI parnum=getval(par); if(bsz!=sz)vec[parnum.F].clear(); while(li+1<pos){ char*child=getstr(li); bsz=sz; PI chnum=getval(child,1); if(bsz!=sz)vec[chnum.F].clear(); vec[parnum.F].pb(chnum.F); } ++pos; } PI ans(0,0); rep(i,sz){ if(ent[i].val.S)continue; PI ti=dfs(ent[i].val.F).F; ans.F+=ti.F; ans.S+=ti.S; } int ns=(ans.F-fami*ans.S)/(sing-fami); int nf=(ans.F-sing*ans.S)/(fami-sing); printf("%d. %d %d %d\n",++k,ns,nf,ans.F); } }