Artifact Content
Not logged in

Artifact 1dd2adf40bd7c456b30f9bc3fccf898f17082c04


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class CssRules { public:
	int getMinimalCssRuleCount(vector <string> xthml) 
	{
		tree virtual_root;
		{
			num_node = 0;
			string xs = accumulate(xthml.begin(), xthml.end(), string(""));
			const char* p = xs.c_str();
			virtual_root.children = parse_tags(p);
		}
		vector<int> memo(num_node*8*8*8, -1);
		return rec(virtual_root.children, 7*64+7*8+7, memo);
	}

	struct tree
	{
		int id;
		int tag;
		int color;
		vector<tree*> children;
		~tree() { for(int i=0; i<children.size(); ++i) delete children[i]; }
	};

	// solver -------------------------------------------------------------

	int rec(vector<tree*>& ts, int tag_to_color, vector<int>& memo)
	{
		int sum = 0;
		for(int i=0; i<ts.size(); ++i)
			sum += rec(ts[i], tag_to_color, memo);
		return sum;
	}

	int rec(tree* t, int tag_to_color, vector<int>& memo)
	{
		const int key = t->id * 8*8*8 + tag_to_color;
		if( memo[key] >= 0 )
			return memo[key];

		int me   = ((tag_to_color>>(3*t->tag))&7) != t->color;
		int best = 0x3fffffff;
		for(int ttc=0; ttc<8*8*8; ++ttc)
		{
			int cost = 0;
			cost += ((tag_to_color>>0)&7) != ((ttc>>0)&7);
			cost += ((tag_to_color>>3)&7) != ((ttc>>3)&7);
			cost += ((tag_to_color>>6)&7) != ((ttc>>6)&7);
			best = min(best, cost + srec(t->children, ttc, memo));
		}
		return memo[key] = me + best;
	}

	// parser ------------------------------------------------------

	int num_node;

	vector<tree*> parse_tags( const char*& p )
	{
		vector<tree*> res;
		while(*p && p[1]!='/')
			res.push_back(parse_tag(p));
		return res;
	}

	tree* parse_tag( const char*& p )
	{
		static map<string, int> color_map;
		if( color_map.empty() )
		{
			color_map["black"]  = 0;
			color_map["blue"]   = 1;
			color_map["gray"]   = 2;
			color_map["green"]  = 3;
			color_map["red"]    = 4;
			color_map["white"]  = 5;
			color_map["yellow"] = 6;
		}
		static map<string, int> tag_map;
		if( tag_map.empty() )
		{
			tag_map["b"] = 0;
			tag_map["u"] = 1;
			tag_map["i"] = 2;
		}

		// <TAG id='ID' style='color:COLOR'>tagContent</TAG>
		p++;                                  // <
		string tag; while(*p!=' ') tag+=*p++; // TAG
		while(*p==' ') ++p;                   // _sp_
		p += 4;                               // id='
		string id;  while(*p!='\'') id+=*p++; // ID
		++p;                                  // '
		while(*p==' ') ++p;                   // _sp_
		p += 13;                              // style='color:
		string cl;  while(*p!='\'') cl+=*p++; // COLOR
		p += 2;                               // '>
		vector<tree*> ch = parse_tags(p);     // tagContent
		p += 4;                               // </TAG>

		tree* t = new tree;
		t->id       = num_node++;
		t->tag      = tag_map[tag];
		t->color    = color_map[cl];
		t->children = ch;
		return t;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, CssRules().getMinimalCssRuleCount(xthml));}
int main(){

CASE(6)
	string xthml_[] = {"<i id='b' style='color:white'><u id='f' styl", "e='color:red'></u><u id='e' style='color:red", "'></u><u id='d' style='color:gray'></u><i id", "='c' style='color:white'></i></i><i id='a' s", "tyle='color:red'></i>"};
	  vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_)); 
	int _ = 5; 
END
CASE(0)
	string xthml_[] = {"<b id='x' style='color:red'></b>"};
	  vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_)); 
	int _ = 1; 
END
CASE(1)
	string xthml_[] = {"<b id='x' style='color:red'>","<b id='y' style='color:red'>",
 "<b id='z' style='color:red'>","</b></b></b>"}
;
	  vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_)); 
	int _ = 2; 
END
CASE(2)
	string xthml_[] = {"<b id='x' style='color:red'>",
"<b id='y' style='color:red'>",
"<b id='w' style='color:red'>",
"</b>",
"</b>",
"<u id='z' style='color:red'>",
"</u>",
"</b>"};
	  vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_)); 
	int _ = 3; 
END
CASE(3)
	string xthml_[] = {"<b id='x' style='color:red'>",
"<i id='y' style='color:black'>",
"<u id='w' style='color:white'>",
"</u>",
"</i>",
"<u id='z' style='color:yellow'>",
"</u>",
"</b>"};
	  vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_)); 
	int _ = 4; 
END
CASE(4)
	string xthml_[] = {"<b id='x' style='col", "or:red'></b>", "<b id=", "'xx' style='color", ":red'></b>"};
	  vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_)); 
	int _ = 2; 
END
CASE(5)
	string xthml_[] = {
"<b id='aa' style='color:red'><b id='ab' style='col",
"or:red'><b id='ac' style='color:red'><b id='ad' st",
"yle='color:red'><b id='ae' style='color:red'><b id",
"='af' style='color:red'><b id='ag' style='color:re",
"d'><b id='ah' style='color:red'><b id='ai' style='",
"color:red'><b id='aj' style='color:red'><b id='ak'",
" style='color:red'><b id='al' style='color:red'><b",
" id='am' style='color:red'><b id='an' style='color",
":red'><b id='ao' style='color:red'><b id='ap' styl",
"e='color:red'><b id='aq' style='color:red'><b id='",
"ar' style='color:red'><b id='as' style='color:red'",
"><b id='at' style='color:red'><b id='au' style='co",
"lor:red'><b id='av' style='color:red'><b id='aw' s",
"tyle='color:red'><b id='ax' style='color:red'><b i",
"d='ay' style='color:red'><b id='az' style='color:r",
"ed'><b id='ba' style='color:red'><b id='bb' style=",
"'color:red'><b id='bc' style='color:red'><b id='bd",
"' style='color:red'><b id='be' style='color:red'><",
"b id='bf' style='color:red'><b id='bg' style='colo",
"r:red'><b id='bh' style='color:red'><b id='bi' sty",
"le='color:red'><b id='bj' style='color:red'><b id=",
"'bk' style='color:red'><b id='bl' style='color:red",
"'><b id='bm' style='color:red'><b id='bn' style='c",
"olor:red'><b id='bo' style='color:red'><b id='bp' ",
"style='color:red'><b id='bq' style='color:red'><b ",
"id='br' style='color:red'><b id='bs' style='color:",
"red'><b id='bt' style='color:red'><b id='bu' style",
"='color:red'><b id='bv' style='color:red'><b id='b",
"w' style='color:red'><b id='bx' style='color:red'>",
"<b id='by' style='color:red'><b id='bz' style='col",
"or:red'><b id='ca' style='color:red'><b id='cb' st",
"yle='color:red'><b id='cc' style='color:red'><b id",
"='cd' style='color:red'><b id='ce' style='color:re",
"d'><b id='cf' style='color:red'><b id='cg' style='",
"color:red'><b id='ch' style='color:red'><b id='ci'",
" style='color:red'><b id='cj' style='color:red'><b",
" id='ck' style='color:red'><b id='cl' style='color",
":red'><b id='cm' style='color:red'><b id='cn' styl",
"e='color:red'><b id='co' style='color:red'><b id='",
"cp' style='color:red'><b id='cq' style='color:red'",
"><b id='cr' style='color:red'><b id='cs' style='co",
"lor:red'><b id='ct' style='color:red'><b id='cu' s",
"tyle='color:red'><b id='cv' style='color:red'><b i",
"d='cw' style='color:red'></b></b></b></b></b></b><",
"/b></b></b></b></b></b></b></b></b></b></b></b></b",
"></b></b></b></b></b></b></b></b></b></b></b></b><",
"/b></b></b></b></b></b></b></b></b></b></b></b></b",
"></b></b></b></b></b></b></b></b></b></b></b></b><",
"/b></b></b></b></b></b></b></b></b></b></b></b></b",
"></b></b></b></b></b></b>"
};
	  vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_)); 
	int _ = -1; 
END
}
// END CUT HERE