Codeforces 89 B. Widget Library

Codeforces 実装問題

問題

Widgetを作るライブラリがあり、次のような命令をもつ。

  • Widget name(x,y) 名前がnameで幅x高さyのWidgetを作る
  • Hbox name 名前がnameのHboxを作る
  • Vbox name 名前がnameのVboxを作る
  • name1.pack(name2) 名前がname1のウィジェットの中にname2のウィジェットを入れる
  • name.set_border(x) 名前がnameのウィジェットのボーダーをセットする
  • name.set_spacing(x) 名前がnameのウィジェットのスペースをセットする

Hbox,Vboxは、内部にウィジェットを複数持つことができるウィジェットで、
Hboxは横に、Vboxは縦に要素が、spacingの間隔をあけて並ぶ。
spacingとは別に、borderの幅だけ、ウィジェットの幅は大きくなる。
（詳細は本文中の図を参照）


内部に何もWidgetをもたないHbox,Vboxは、border,spacingの値にかかわらず、
幅、高さがともに0になるものとする。


Widgetを作る命令列が与えられたとき、各ウィジェットの幅および高さを出力せよ。
出力はWidgetの名前が昇順になるようにせよ。

制約条件

命令の数≦100

方針

がんばってparseして、最後に幅と高さをDFSして計算する。
計算した幅と高さはメモ化しておく。

ソースコード

struct S{
	string type,name;
	ll w,h,b,s;
	vi cld;
};
S widget[101];
int n,sz;

pi rec(int c){
	ll &w=widget[c].w, &h=widget[c].h;
	if(w>=0)return mp(w,h);
	w=0; h=0;
	rep(i,widget[c].cld.size()){
		pi p=rec(widget[c].cld[i]);
		if(widget[c].type=="H"){
			h=max(h,p.second);
			w+=(i?widget[c].s:0)+p.first;
		}
		else{
			w=max(w,p.first);
			h+=(i?widget[c].s:0)+p.second;
		}
	}
	if(widget[c].cld.size()){
		w+=2*widget[c].b; h+=2*widget[c].b;
	}
	return mp(w,h);
}

void run()
{
	string in;
	getline(cin,in);
	n=atoi(in.c_str());
	sz=0;
	rep(i,n)widget[i].w=widget[i].h=-1;
	
	rep(it,n){
		getline(cin,in);
		rep(i,in.size())if(!isalnum(in[i]))in[i]=' ';
		stringstream ss(in);
		ss>>in;
		if(in[0]=='W'){
			ss>>widget[sz].name>>widget[sz].w>>widget[sz].h;
			widget[sz++].type="W";
		}
		else if(in[0]=='V'||in[0]=='H'){
			ss>>widget[sz].name;
			widget[sz++].type=in.substr(0,1);
		}
		else{
			string method;
			ss>>method;
			if(method[0]=='s'){
				ss>>method;
				ll x; ss>>x;
				rep(i,sz)if(widget[i].name==in){
					if(method[0]=='b')widget[i].b=x;
					else widget[i].s=x;
				}
			}
			else{
				string nm; ss>>nm;
				rep(i,sz)if(widget[i].name==in)
				rep(j,sz)if(widget[j].name==nm){
					widget[i].cld.pb(j); break;
				}
			}
		}
	}
	vs ans;
	rep(i,sz){
		rec(i);
		stringstream ss;
		ss<<widget[i].name<<" "<<widget[i].w<<" "<<widget[i].h;
		ans.pb(ss.str());
	}
	sort(all(ans));
	rep(i,ans.size())cout<<ans[i]<<endl;
}