fork download
copy 
  1. #include <vector>
  2. #include <string>
  3. #include <map>
  4. #include <set>
  5. #include <algorithm>
  6.  
  7. typedef unsigned long long uint64_t;
  8. typedef unsigned int uint32_t;
  9.  
  10. typedef std::vector<int> vector_int_t;
  11. typedef std::string string8_t;
  12.  
  13. class TurnOnLampsDmitriyH
  14. { 
  15.     struct road_t 
  16. 	{ 
  17. 		road_t(): to(0), id(0), isImp(0) {} 
  18. 		road_t(size_t to_, size_t id_, uint32_t isImp_): to(to_), id(id_), isImp(isImp_) {} 
  19.  
  20. 		size_t to; 
  21. 		size_t id; 
  22. 		uint32_t isImp; 
  23. 	}; 
  24.  
  25. 	typedef std::vector<road_t> vector_road_t; 
  26. 	typedef std::vector<vector_road_t> vector_2d_road_t; 
  27. 	typedef std::vector<uint64_t> vector_uint64_t; 
  28. 	typedef std::vector<vector_uint64_t> vector_2d_uint64_t; 
  29. 	typedef std::set<uint64_t> set_uint64_t; 
  30.  
  31. 	void Walk(const vector_2d_road_t& links, const string8_t& isImportant, vector_int_t& wasHere, const size_t initialId, const size_t startId, const uint64_t currentChain, vector_2d_uint64_t& switchMask) 
  32. 	{ 
  33. 		switchMask[initialId][startId] = currentChain; 
  34. 		wasHere[startId] = 1; 
  35.  
  36. 		const vector_road_t& link = links[startId]; 
  37. 		for (size_t i = 0; i < link.size(); i++) 
  38. 		{ 
  39. 			const size_t nextId = link[i].to; 
  40. 			const uint32_t isImp = link[i].isImp; 
  41. 			if (wasHere[nextId]) 
  42. 				continue; 
  43.  
  44. 			uint64_t chain = currentChain; 
  45. 			if (isImp) 
  46. 				chain |= (1ULL << link[i].id); 
  47.  
  48. 			Walk(links, isImportant, wasHere, initialId, nextId, chain, switchMask); 
  49. 		} 
  50. 	} 
  51.  
  52. 	uint64_t GetIntersectCount(const uint64_t x, const uint64_t y) 
  53. 	{ 
  54. 		uint64_t ans = 0; 
  55. 		if (x == y) 
  56. 			return 100; 
  57. 		for (size_t i = 0; i < 63; i++) 
  58. 		{ 
  59. 			const uint64_t d = 1ULL << i; 
  60. 			if ((x & d) && (y & d)) 
  61. 				ans++; 
  62. 		} 
  63. 		return ans; 
  64. 	} 
  65.  
  66. public: 
  67. 	int minimize(vector_int_t roads, string8_t initState, string8_t isImportant) 
  68. 	{ 
  69. 		const size_t n = roads.size() + 1; 
  70. 		vector_2d_road_t links(n); 
  71.  
  72. 		for (size_t i = 0; i + 1 < n; i++) 
  73. 		{ 
  74. 			const size_t a = i + 1; 
  75. 			const size_t b = roads[i]; 
  76. 			const size_t id = i; 
  77. 			const uint32_t isImp = isImportant[i] == '1' ? 1 : 0; 
  78. 			links[a].push_back(road_t(b, id, isImp)); 
  79. 			links[b].push_back(road_t(a, id, isImp)); 
  80. 		} 
  81.  
  82. 		uint64_t requiredMask = 0; 
  83. 		for (size_t i = 0; i + 1 < n; i++) 
  84. 		{ 
  85. 			if (isImportant[i] == '1' && initState[i] == '0') 
  86. 			{ 
  87. 				requiredMask |= (1ULL << i); 
  88. 			} 
  89. 		} 
  90.  
  91. 		vector_2d_uint64_t switchMask(n, vector_uint64_t(n)); 
  92. 		for (size_t i = 0; i < n; i++) 
  93. 		{ 
  94. 			vector_int_t wasHere(n); 
  95. 			Walk(links, isImportant, wasHere, i, i, 0ULL, switchMask); 
  96. 		} 
  97.  
  98. 		set_uint64_t options; 
  99. 		for (size_t i = 0; i < n; i++) 
  100. 		{ 
  101. 			for (size_t j = 0; j < n; j++) 
  102. 			{ 
  103. 				options.insert(switchMask[i][j]); 
  104. 			} 
  105. 		} 
  106. 		options.erase(0); 
  107.  
  108. 		uint32_t ans = 0; 
  109. 		uint64_t currentMask = requiredMask; 
  110. 		while (currentMask) 
  111. 		{ 
  112. 			for (size_t i = 0; i < n; i++) 
  113. 			{ 
  114. 				if (currentMask & (1ULL << i)) 
  115. 				{ 
  116. 					uint64_t bestMatch = 0; 
  117. 					uint64_t bestMask = 0; 
  118. 					for (set_uint64_t::const_iterator pi = options.begin(); pi != options.end(); ++pi) 
  119. 					{ 
  120. 						const uint64_t nextMask = *pi; 
  121. 						if (currentMask & nextMask) 
  122. 						{ 
  123. 							const uint64_t cnt = GetIntersectCount(currentMask, nextMask); 
  124. 							if (cnt > bestMatch) 
  125. 							{ 
  126. 								bestMatch = cnt; 
  127. 								bestMask = nextMask; 
  128. 							} 
  129. 						} 
  130. 					} 
  131.  
  132. 					currentMask ^= bestMask; 
  133. 					ans += 1; 
  134. 				} 
  135. 			} 
  136. 		} 
  137.  
  138. 		return ans; 
  139. 	} 
  140. };
  141.  
  142.  
  143.  
  144.  
  145. using namespace std; 
  146. #define pb push_back 
  147. #define INF 1000000000 
  148. #define L(s) (int)((s).size()) 
  149. #define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++) 
  150. #define rep(i,n) FOR(i,1,(n)) 
  151. #define rept(i,n) FOR(i,0,(n)-1) 
  152. #define C(a) memset((a),0,sizeof(a)) 
  153. #define ll long long 
  154. #define all(c) (c).begin(), (c).end() 
  155. #define SORT(c) sort(all(c)) 
  156. #define VI vector<int> 
  157. #define ppb pop_back 
  158. #define mp make_pair 
  159. #define pii pair<int,int> 
  160. #define x first 
  161. #define y second 
  162.  
  163. vector<pii> sm[51]; 
  164. VI mem[51]; 
  165. int n; 
  166.  
  167. void rec(int v, int pr) { 
  168. 	if (L(mem[v])) return; 
  169. 	if (L(sm[v]) == 1 && pr != -1) { 
  170. 		mem[v].resize(n + 1); 
  171. 		rept(i, L(mem[v])) mem[v][i] = i; 
  172. 		return; 
  173. 	} 
  174. 	VI cur(n + 1, 0); 
  175. 	rept(i, L(cur)) cur[i] = i; 
  176. 	rept(i, L(sm[v])) { 
  177. 		int w = sm[v][i].x; 
  178. 		if (w == pr) continue; 
  179. 		rec(w, v); 
  180. 		VI t = mem[w]; 
  181. 		VI nt(L(t), INF); 
  182. 		rept(j, L(t)) { 
  183. 			FOR(add, -L(t), L(t)) { 
  184. 				if (j + add < 0 || j + add >= L(t)) continue; 
  185. 				if (sm[v][i].y != -1 && (j + add) % 2 != sm[v][i].y % 2) continue; 
  186. 				nt[j + add] = min(nt[j + add], t[j] + (add > 0 ? add : 0)); 
  187. 			} 
  188. 		} 
  189. 		t = nt; 
  190. 		nt = VI(L(t), INF); 
  191. 		rept(j, L(t)) { 
  192. 			FOR(add, -L(t), L(t)) { 
  193. 				if (j + add < 0 || j + add >= L(t)) continue; 
  194. 				nt[j + add] = min(nt[j + add], t[j] + (add > 0 ? add : 0)); 
  195. 			} 
  196. 		} 
  197. 		VI ncur(L(cur), INF); 
  198. 		rept(now, L(nt)) { 
  199. 			rept(old, L(cur)) { 
  200. 				if (now + old - 2 * min(now, old) < L(ncur)) { 
  201. 					ncur[now + old - 2 * min(now, old)] = min(ncur[now + old - 2 * min(now, old)], cur[old] + nt[now] - min(old, now)); 
  202. 				} 
  203. 			} 
  204. 		} 
  205. 		cur = ncur; 
  206. 	} 
  207. 	mem[v] = cur; 
  208. } 
  209.  
  210. class TurnOnLampsKADR
  211. { 
  212. public: 
  213. 	TurnOnLampsKADR
  214. 		()
  215. 	{
  216. 		for (size_t i = 0; i < 51; i++)
  217. 		{
  218. 			sm[i].clear();
  219. 			mem[i].clear();
  220. 		}
  221.  
  222. 		n = 0;
  223. 	}
  224. 	int minimize( vector <int> roads, string initState, string isImportant ) 
  225. 	{ 
  226. 		rept(i, 51) sm[i].clear(); 
  227. 		n = L(roads) + 1; 
  228. 		rept(i, L(roads)) { 
  229. 			int a = roads[i]; 
  230. 			int b = i + 1; 
  231. 			if (isImportant[i] == '1') { 
  232. 				int t = 0; 
  233. 				if (initState[i] == '1') t = 0; else 
  234. 					t = 1; 
  235. 				sm[a].pb(mp(b, t)); 
  236. 				sm[b].pb(mp(a, t)); 
  237. 			} else { 
  238. 				sm[a].pb(mp(b, -1)); 
  239. 				sm[b].pb(mp(a, -1)); 
  240. 			} 
  241. 		} 
  242. 		rept(i, 51) mem[i].clear(); 
  243. 		int ans = INF; 
  244. 		rec(0, -1); 
  245. 		rept(i, L(mem[0])) { 
  246. 			ans = min(ans, mem[0][i]); 
  247. 		} 
  248. 		return ans; 
  249. 	} 
  250. }; 
  251.  
  252.  
  253. #include <iostream>
  254. #include <iomanip>
  255. #include <ctime>
  256.  
  257. template<typename T> inline T Max(const T a, const T b) {return a > b ? a : b;}
  258. template<typename T> inline void UpdateMax(T& a, const T b) {a = Max(a, b);}
  259.  
  260. template<typename T> inline std::ostream& operator<<(std::ostream& ost, const std::vector<T>& data)
  261. {
  262. 	for (size_t i = 0; i < data.size(); i++) { if (i != 0) { ost << ' '; } ost << data[i]; }
  263. 	return ost;
  264. }
  265.  
  266. struct stats_t
  267. {
  268. 	stats_t()
  269. 	{
  270. 		m_timeStart = clock();
  271. 		testsPassed = 0;
  272. 		maxMovesCount = 0;
  273. 	}
  274.  
  275. 	void Print()
  276. 	{
  277. 		const clock_t timeStop(clock());
  278. 		const unsigned long long durationMs = (((unsigned long long)1000 * (timeStop - m_timeStart) + CLOCKS_PER_SEC - 1) / CLOCKS_PER_SEC);
  279.  
  280. 		std::cout << "Time elapsed : " << setw(10) << durationMs / 1000 << " s " << setw(3) << durationMs % 1000 << " ms"
  281. 			<< ", tests passed: " << std::setw(10) << testsPassed << ", max moves: " << std::setw(4) << maxMovesCount << std::endl;
  282. 	}
  283.  
  284. 	clock_t m_timeStart;
  285. 	uint64_t testsPassed;
  286. 	int maxMovesCount;
  287. };
  288.  
  289. stats_t g_stats;
  290.  
  291. void Test()
  292. {
  293. 	clock_t lastPrintTime(clock());
  294.  
  295. 	const size_t TestCount = 3000;
  296. 	const size_t MaxLen = 50;
  297.  
  298. 	int errorsCount = 0;
  299.  
  300. 	for (size_t t = 0; t < TestCount; t++)
  301. 	{
  302. 		const size_t len = rand() % (MaxLen - 1) + 2;
  303. 		vector_int_t roads(len - 1);
  304. 		for (size_t i = 0; i < roads.size(); i++)
  305. 		{
  306. 			roads[i] = rand() % (i + 1);
  307. 		}
  308.  
  309. 		string8_t initialState(len - 1, '0');
  310. 		string8_t isImportant(len - 1, '0');
  311.  
  312. 		for (size_t i = 0; i + 1 < len; i++)
  313. 		{
  314. 			initialState[i] = rand() % 2 + '0';
  315. 			isImportant[i] = rand() % 2 + '0';
  316. 		}
  317.  
  318. 		if (rand() % 2 == 1)
  319. 			string8_t(isImportant.size(), '1').swap(isImportant);
  320.  
  321. 		TurnOnLampsDmitriyH mySolution;
  322. 		TurnOnLampsKADR othersSolution1;
  323.  
  324. 		const int myAns = mySolution.minimize(roads, initialState, isImportant);
  325. 		const int refAns = othersSolution1.minimize(roads, initialState, isImportant);
  326.  
  327. 		g_stats.testsPassed += 1;
  328. 		UpdateMax(g_stats.maxMovesCount, myAns);
  329.  
  330. 		clock_t currentTime(clock());
  331. 		const unsigned long long msFromLastPrint = (((unsigned long long)1000 * (currentTime - lastPrintTime) + CLOCKS_PER_SEC - 1) / CLOCKS_PER_SEC);
  332. 		if (msFromLastPrint > 1000)
  333. 		{
  334. 			g_stats.Print();
  335. 			lastPrintTime = currentTime;
  336. 		}
  337.  
  338. 		if (myAns != refAns)
  339. 		{
  340. 			errorsCount += 1;
  341. 			std::cout << "Failed test case (id=" << t << ")" << std::endl;
  342. 			std::cout << "Expected ans = " << refAns << ", actual ans = " << myAns << std::endl;
  343. 			std::cout << len << std::endl;
  344. 			std::cout << roads << std::endl;
  345. 			std::cout << initialState << std::endl;
  346. 			std::cout << isImportant << std::endl;
  347. 			std::cout << "errorsCount = " << errorsCount << std::endl;
  348. 			std::cout << std::endl;
  349. 		}
  350. 	}
  351.  
  352. 	g_stats.Print();	
  353. 	std::cout << "errorsCount = " << errorsCount << std::endl;	
  354. }
  355.  
  356. int main()
  357. {
  358. 	srand(0);
  359. 	Test();
  360. 	return 0;
  361. }
Success #stdin #stdout 4.19s 3004KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Time elapsed :          1 s  10 ms, tests passed:        723, max moves:   17
Time elapsed :          2 s  20 ms, tests passed:       1460, max moves:   17
Time elapsed :          3 s  30 ms, tests passed:       2180, max moves:   17
Time elapsed :          4 s  40 ms, tests passed:       2889, max moves:   17
Time elapsed :          4 s 180 ms, tests passed:       3000, max moves:   17
errorsCount = 0
https://ideone.com/uNo8rD
tc 500 test
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!