006cf643bb 2013-06-22 kinaba: #include <iostream> 006cf643bb 2013-06-22 kinaba: #include <sstream> 006cf643bb 2013-06-22 kinaba: #include <iomanip> 006cf643bb 2013-06-22 kinaba: #include <vector> 006cf643bb 2013-06-22 kinaba: #include <string> 006cf643bb 2013-06-22 kinaba: #include <map> 006cf643bb 2013-06-22 kinaba: #include <set> 006cf643bb 2013-06-22 kinaba: #include <algorithm> 006cf643bb 2013-06-22 kinaba: #include <numeric> 006cf643bb 2013-06-22 kinaba: #include <iterator> 006cf643bb 2013-06-22 kinaba: #include <functional> 006cf643bb 2013-06-22 kinaba: #include <complex> 006cf643bb 2013-06-22 kinaba: #include <queue> 006cf643bb 2013-06-22 kinaba: #include <stack> 006cf643bb 2013-06-22 kinaba: #include <cmath> 006cf643bb 2013-06-22 kinaba: #include <cassert> 006cf643bb 2013-06-22 kinaba: using namespace std; 006cf643bb 2013-06-22 kinaba: typedef long long LL; 006cf643bb 2013-06-22 kinaba: typedef long double LD; 006cf643bb 2013-06-22 kinaba: typedef complex<double> CMP; 006cf643bb 2013-06-22 kinaba: 006cf643bb 2013-06-22 kinaba: class TurnOnLamps { public: 006cf643bb 2013-06-22 kinaba: typedef int Vert; 006cf643bb 2013-06-22 kinaba: struct Edge { 006cf643bb 2013-06-22 kinaba: bool init; 006cf643bb 2013-06-22 kinaba: bool goal; 006cf643bb 2013-06-22 kinaba: Vert from; 006cf643bb 2013-06-22 kinaba: Vert to; 006cf643bb 2013-06-22 kinaba: }; 006cf643bb 2013-06-22 kinaba: 006cf643bb 2013-06-22 kinaba: int minimize(vector <int> roads, string initState, string isImportant) 006cf643bb 2013-06-22 kinaba: { 006cf643bb 2013-06-22 kinaba: int N = roads.size() + 1; 006cf643bb 2013-06-22 kinaba: vector< vector<Edge> > G(N); 006cf643bb 2013-06-22 kinaba: for(int i=0; i<roads.size(); ++i) 006cf643bb 2013-06-22 kinaba: { 006cf643bb 2013-06-22 kinaba: int v = i+1; 006cf643bb 2013-06-22 kinaba: int u = roads[i]; 006cf643bb 2013-06-22 kinaba: {Edge e = {initState[i]=='1', isImportant[i]=='1', v, u}; G[v].push_back(e);} 006cf643bb 2013-06-22 kinaba: {Edge e = {initState[i]=='1', isImportant[i]=='1', u, v}; G[u].push_back(e);} 006cf643bb 2013-06-22 kinaba: } 006cf643bb 2013-06-22 kinaba: 006cf643bb 2013-06-22 kinaba: Edge e = {false, false, -1, 0}; 006cf643bb 2013-06-22 kinaba: pair<int,int> rr = rec(e, G); 006cf643bb 2013-06-22 kinaba: return min(rr.first, rr.second); 006cf643bb 2013-06-22 kinaba: } 006cf643bb 2013-06-22 kinaba: 006cf643bb 2013-06-22 kinaba: static const int INF = 999999; 006cf643bb 2013-06-22 kinaba: 006cf643bb 2013-06-22 kinaba: // not use, use 006cf643bb 2013-06-22 kinaba: pair<int,int> rec(Edge e, vector<vector<Edge> >& G) 006cf643bb 2013-06-22 kinaba: { 006cf643bb 2013-06-22 kinaba: vector< pair<int,int> > p; 006cf643bb 2013-06-22 kinaba: for(int i=0; i<G[e.to].size(); ++i) 006cf643bb 2013-06-22 kinaba: { 006cf643bb 2013-06-22 kinaba: Edge& e2 = G[e.to][i]; 006cf643bb 2013-06-22 kinaba: if(e2.to != e.from) 006cf643bb 2013-06-22 kinaba: p.push_back(rec(e2, G)); 006cf643bb 2013-06-22 kinaba: } 006cf643bb 2013-06-22 kinaba: pair<int,int> r = calc_on_node(p); 006cf643bb 2013-06-22 kinaba: if(e.goal) 006cf643bb 2013-06-22 kinaba: (e.init ? r.second : r.first) = INF; 006cf643bb 2013-06-22 kinaba: return r; 006cf643bb 2013-06-22 kinaba: } 006cf643bb 2013-06-22 kinaba: 006cf643bb 2013-06-22 kinaba: pair<int,int> calc_on_node(vector<pair<int,int> >& c) 006cf643bb 2013-06-22 kinaba: { 006cf643bb 2013-06-22 kinaba: int nu = calc(c); 006cf643bb 2013-06-22 kinaba: int u = (c.empty() ? 1 : INF); 006cf643bb 2013-06-22 kinaba: for(int i=0; i<c.size(); ++i) 006cf643bb 2013-06-22 kinaba: { 006cf643bb 2013-06-22 kinaba: vector<pair<int,int> > cc = c; 006cf643bb 2013-06-22 kinaba: cc.erase(cc.begin() + i); 006cf643bb 2013-06-22 kinaba: int s1 = calc(cc); 006cf643bb 2013-06-22 kinaba: int s2 = min(c[i].first + 1, c[i].second); 006cf643bb 2013-06-22 kinaba: u = min(u, s1+s2); 006cf643bb 2013-06-22 kinaba: } 006cf643bb 2013-06-22 kinaba: return make_pair(nu, u); 006cf643bb 2013-06-22 kinaba: } 006cf643bb 2013-06-22 kinaba: 006cf643bb 2013-06-22 kinaba: int calc(vector<pair<int,int> >& c) 006cf643bb 2013-06-22 kinaba: { 006cf643bb 2013-06-22 kinaba: int od = INF; 006cf643bb 2013-06-22 kinaba: int ev = 0; 006cf643bb 2013-06-22 kinaba: for(int i=0; i<c.size(); ++i) 006cf643bb 2013-06-22 kinaba: { 006cf643bb 2013-06-22 kinaba: int c0 = c[i].first; 006cf643bb 2013-06-22 kinaba: int c1 = c[i].second; 006cf643bb 2013-06-22 kinaba: 006cf643bb 2013-06-22 kinaba: int od2 = min(ev+c1, od+c0); 006cf643bb 2013-06-22 kinaba: int ev2 = min(ev+c0, od+c1-1); 006cf643bb 2013-06-22 kinaba: od = od2, ev = ev2; 006cf643bb 2013-06-22 kinaba: } 006cf643bb 2013-06-22 kinaba: return min(od, ev); 006cf643bb 2013-06-22 kinaba: } 006cf643bb 2013-06-22 kinaba: }; 006cf643bb 2013-06-22 kinaba: 006cf643bb 2013-06-22 kinaba: // BEGIN CUT HERE 006cf643bb 2013-06-22 kinaba: #include <ctime> 006cf643bb 2013-06-22 kinaba: double start_time; string timer() 006cf643bb 2013-06-22 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 006cf643bb 2013-06-22 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 006cf643bb 2013-06-22 kinaba: { os << "{ "; 006cf643bb 2013-06-22 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 006cf643bb 2013-06-22 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 006cf643bb 2013-06-22 kinaba: void verify_case(const int& Expected, const int& Received) { 006cf643bb 2013-06-22 kinaba: bool ok = (Expected == Received); 006cf643bb 2013-06-22 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 006cf643bb 2013-06-22 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 006cf643bb 2013-06-22 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 006cf643bb 2013-06-22 kinaba: #define END verify_case(_, TurnOnLamps().minimize(roads, initState, isImportant));} 006cf643bb 2013-06-22 kinaba: int main(){ 006cf643bb 2013-06-22 kinaba: 006cf643bb 2013-06-22 kinaba: CASE(0) 006cf643bb 2013-06-22 kinaba: int roads_[] = {0,0,1,1}; 006cf643bb 2013-06-22 kinaba: vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 006cf643bb 2013-06-22 kinaba: string initState = "0001"; 006cf643bb 2013-06-22 kinaba: string isImportant = "0111"; 006cf643bb 2013-06-22 kinaba: int _ = 1; 006cf643bb 2013-06-22 kinaba: END 006cf643bb 2013-06-22 kinaba: CASE(1) 006cf643bb 2013-06-22 kinaba: int roads_[] = {0,0,1,1}; 006cf643bb 2013-06-22 kinaba: vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 006cf643bb 2013-06-22 kinaba: string initState = "0000"; 006cf643bb 2013-06-22 kinaba: string isImportant = "0111"; 006cf643bb 2013-06-22 kinaba: int _ = 2; 006cf643bb 2013-06-22 kinaba: END 006cf643bb 2013-06-22 kinaba: CASE(2) 006cf643bb 2013-06-22 kinaba: int roads_[] = {0,0,1,1,4,4}; 006cf643bb 2013-06-22 kinaba: vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 006cf643bb 2013-06-22 kinaba: string initState = "000100"; 006cf643bb 2013-06-22 kinaba: string isImportant = "111111"; 006cf643bb 2013-06-22 kinaba: int _ = 2; 006cf643bb 2013-06-22 kinaba: END 006cf643bb 2013-06-22 kinaba: CASE(3) 006cf643bb 2013-06-22 kinaba: int roads_[] = {0,0,1,1,4,4}; 006cf643bb 2013-06-22 kinaba: vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 006cf643bb 2013-06-22 kinaba: string initState = "100100"; 006cf643bb 2013-06-22 kinaba: string isImportant = "011101"; 006cf643bb 2013-06-22 kinaba: int _ = 2; 006cf643bb 2013-06-22 kinaba: END 006cf643bb 2013-06-22 kinaba: CASE(4) 006cf643bb 2013-06-22 kinaba: int roads_[] = {0,0,2,2,3,1,6,3,1}; 006cf643bb 2013-06-22 kinaba: vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 006cf643bb 2013-06-22 kinaba: string initState = "010001110"; 006cf643bb 2013-06-22 kinaba: string isImportant = "000110100"; 006cf643bb 2013-06-22 kinaba: int _ = 1; 006cf643bb 2013-06-22 kinaba: END 006cf643bb 2013-06-22 kinaba: CASE(5) 006cf643bb 2013-06-22 kinaba: int roads_[] = {0,0,1,2,4,4,6,1,2,5,2,8,8,3,6,4,14,7,18,14,11,7,1,12,7,5,18,23,0,14,11,10,2,2,6,1,30,11,9,12,5,35,25,11,23,17,14,45,15}; 006cf643bb 2013-06-22 kinaba: vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 006cf643bb 2013-06-22 kinaba: string initState = "0000000000010000000000000010000010100000000000000"; 006cf643bb 2013-06-22 kinaba: string isImportant = "1010111111111011011111000110111111111111111110111"; 006cf643bb 2013-06-22 kinaba: int _ = 14; 006cf643bb 2013-06-22 kinaba: END 006cf643bb 2013-06-22 kinaba: /* 006cf643bb 2013-06-22 kinaba: CASE(6) 006cf643bb 2013-06-22 kinaba: int roads_[] = ; 006cf643bb 2013-06-22 kinaba: vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 006cf643bb 2013-06-22 kinaba: string initState = ; 006cf643bb 2013-06-22 kinaba: string isImportant = ; 006cf643bb 2013-06-22 kinaba: int _ = ; 006cf643bb 2013-06-22 kinaba: END 006cf643bb 2013-06-22 kinaba: CASE(7) 006cf643bb 2013-06-22 kinaba: int roads_[] = ; 006cf643bb 2013-06-22 kinaba: vector <int> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 006cf643bb 2013-06-22 kinaba: string initState = ; 006cf643bb 2013-06-22 kinaba: string isImportant = ; 006cf643bb 2013-06-22 kinaba: int _ = ; 006cf643bb 2013-06-22 kinaba: END 006cf643bb 2013-06-22 kinaba: */ 006cf643bb 2013-06-22 kinaba: } 006cf643bb 2013-06-22 kinaba: // END CUT HERE