fork download 
  1. #include <ctime>
  2. #include <string>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. const char DELIMITER = '/';																						// Delimiter character for the correct accumulation of order
  9. const unsigned int TIME_CONVERSION_CONSTANT = 1000;																// Used to converting the time, in milliseconds in this case
  10.  
  11. struct Visa {
  12. 	vector <unsigned int> listOfSubordinatesForBribe;															// Storage of subordinates' indices whose signature is required
  13. 	double bribe;																								// Required bribe
  14. };
  15.  
  16. struct Official {
  17. 	unsigned int id;																							// Official id (sequence number in the input stream, starting at one)
  18. 	vector <Visa> listOfRequiredVisas;																			// Storage of possible variants of visas
  19. };
  20.  
  21. bool isBypassed(Official currentOfficial, string order) {														// Return true, if this official is already bypassed
  22. 	bool isBypassed = false;
  23. 	for (auto currentVisa : currentOfficial.listOfRequiredVisas) {
  24. 		for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
  25. 			if (order.find(to_string(currentSubordinate) + DELIMITER) != string::npos) {						// We are looking we are looking for the presence of at least one subordinate including a separator
  26. 				isBypassed = true;            																	// In the string of previously accumulated order of bypass 
  27. 				break;
  28. 			}
  29. 		}
  30. 	}
  31. 	return isBypassed;
  32. }
  33.  
  34. void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &order, unsigned int &minimumBribe) {
  35. 	vector <unsigned int> possibleSumsOfBribes;																	// Stores all the possible sums of bribes for the current official
  36. 	vector <string> possibleOrdersOfBypassing; 																	// Stores all the possible orders for the current of
  37. 	if (!currentOfficial.listOfRequiredVisas.empty() && !isBypassed(currentOfficial, order)) {
  38. 		int currentSumOfBribes = 0;																				// Current sum of bribes for current official
  39. 		for (auto currentVisa : currentOfficial.listOfRequiredVisas) {
  40. 			for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
  41. 				findCheapestWay(listOfOfficials, listOfOfficials[currentSubordinate], order, minimumBribe);		// Recursively call the function for finding the minimum required bribe
  42. 				currentSumOfBribes = minimumBribe;																// Store the detected minimum as a current
  43. 			}																									// For each official we get down to the lower level
  44. 			string currentOrder;																				// Remember all the officials, that we bypassed to the current bribe 
  45. 			currentSumOfBribes = currentVisa.bribe;																// Remember the bribe required by the current official as the current sum of bribes
  46. 			for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
  47. 				currentOrder += to_string(currentSubordinate) + DELIMITER;
  48. 			}																									// Remember the current oder for each visa (isn't necessary an order to get the minimum sum of bribes) with delimiter
  49. 			possibleOrdersOfBypassing.push_back(order + currentOrder);											// Adding one of the possible orders, including previously accumulated value
  50. 			possibleSumsOfBribes.push_back(minimumBribe + currentSumOfBribes);									// Adding one of the possible sums, including value that we get from lower level
  51. 		}																										// Executes processing for each visa in visas list
  52. 		vector<unsigned int>::iterator iteratorToCurrentMinBribe = min_element(possibleSumsOfBribes.begin(), possibleSumsOfBribes.end());
  53. 		unsigned int indexOfCurrentMinBribe = distance(possibleSumsOfBribes.begin(), iteratorToCurrentMinBribe);// Find the index of the lowest possible variant in the resulting vector
  54. 		minimumBribe = possibleSumsOfBribes[indexOfCurrentMinBribe];											// This variant will be the smallest by sum of bribes, remember it
  55. 		order = possibleOrdersOfBypassing[indexOfCurrentMinBribe];												// And remember corresponding to minimum bribe order
  56. 	}																											// Executes processing only if the list of visas isn't empty and the official isn't bypassed
  57. }
  58.  
  59. int main() {
  60. 	clock_t startTime;
  61. 	ios_base::sync_with_stdio(false);
  62. 	string order;																								// The order of bypass, that we're looking for
  63. 	string typeOfCommand;																						// Technical variable for processing the input stream
  64. 	unsigned int quantityOfOfficials;																			// User-defined number of officials
  65. 	unsigned int minimumBribe = 0;																				// Minimum sum of bribes to get a license
  66. 	cin >> quantityOfOfficials;
  67. 	Official *listOfOfficials = new Official[quantityOfOfficials + 1];											// Keeps all the officials in the array with the corresponding index
  68. 	unsigned int indexOfOfficial = 1;
  69. 	while (cin >> typeOfCommand) { 
  70. 		Official currentOfficial;
  71. 		while (typeOfCommand != "next_official") { 
  72. 			Visa currentVisa;
  73. 			vector <unsigned int> requiredSubordinates;
  74. 			while (typeOfCommand != "bribe") { 
  75. 				requiredSubordinates.push_back(atoi(typeOfCommand.c_str()));									// Before recording convert the input string to the number
  76. 				cin >> typeOfCommand;
  77. 			}																									// Read the current visa (indices of subbordinates for bribe)
  78. 			currentVisa.listOfSubordinatesForBribe = requiredSubordinates;
  79. 			cin >> typeOfCommand;																				// Read directly bribe
  80. 			currentVisa.bribe = atoi(typeOfCommand.c_str());													// Before recording convert the input string to the number
  81. 			currentOfficial.listOfRequiredVisas.push_back(currentVisa);											// Add current visa to the current official visas list
  82. 			cin >> typeOfCommand;
  83. 		}																										// Read the current official
  84. 		currentOfficial.id = indexOfOfficial;
  85. 		listOfOfficials[indexOfOfficial] = currentOfficial;														// Put all the read data into an array
  86. 		indexOfOfficial++;																						// Go to read the next official, if present
  87. 	}																											// Read to the end of the input stream
  88. 	findCheapestWay(listOfOfficials, listOfOfficials[1], order, minimumBribe);									// Call the function from main official(first) and accumulate the required values
  89. 	order.push_back('1');																						// Add the first official explicitly, cause he hasn't chief, so doesn't participate in the bypassing
  90. 	cout << minimumBribe << endl << order << endl;
  91. 	cout << "Working time: " << (clock() - startTime) / (double) (CLOCKS_PER_SEC / TIME_CONVERSION_CONSTANT) << " ms" << endl;
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 19048KB
comments (?)
stdin 
1000000
2
bribe
1000000 
next_official 
3
bribe
1000000 
next_official 
4
bribe
1000000 
next_official 
5
bribe
1000000 
next_official 
6
bribe
1000000 
next_official 
7
bribe
1000000 
next_official 
8
bribe
1000000 
next_official 
9
bribe
1000000 
next_official 
10
bribe
1000000 
next_official 
11
bribe
1000000 
next_official 
12
bribe
1000000 
next_official 
13
bribe
1000000 
next_official 
14
bribe
1000000 
next_official 
15
bribe
1000000 
next_official 
16
bribe
1000000 
next_official 
17
bribe
1000000 
next_official 
18
bribe
1000000 
next_official 
19
bribe
1000000 
next_official 
20
bribe
1000000 
next_official 
21
bribe
1000000 
next_official 
22
bribe
1000000 
next_official 
23
bribe
1000000 
next_official 
24
bribe
1000000 
next_official 
25
bribe
1000000 
next_official 
26
bribe
1000000 
next_official 
27
bribe
1000000 
next_official 
28
bribe
1000000 
next_official 
29
bribe
1000000 
next_official 
30
bribe
1000000 
next_official 
31
bribe
1000000 
next_official 
32
bribe
1000000 
next_official 
33
bribe
1000000 
next_official 
34
bribe
1000000 
next_official 
35
bribe
1000000 
next_official 
36
bribe
1000000 
next_official 
37
bribe
1000000 
next_official 
38
bribe
1000000 
next_official 
39
bribe
1000000 
next_official 
40
bribe
1000000 
next_official 
41
bribe
1000000 
next_official 
42
bribe
1000000 
next_official 
43
bribe
1000000 
next_official 
44
bribe
1000000 
next_official 
45
bribe
1000000 
next_official 
46
bribe
1000000 
next_official 
47
bribe
1000000 
next_official 
48
bribe
1000000 
next_official 
49
bribe
1000000 
next_official 
50
bribe
1000000 
next_official 
51
bribe
1000000 
next_official 
52
bribe
1000000 
next_official 
53
bribe
1000000 
next_official 
54
bribe
1000000 
next_official 
55
bribe
1000000 
next_official 
56
bribe
1000000 
next_official 
57
bribe
1000000 
next_official 
58
bribe
1000000 
next_official 
59
bribe
1000000 
next_official 
60
bribe
1000000 
next_official 
61
bribe
1000000 
next_official 
62
bribe
1000000 
next_official 
63
bribe
1000000 
next_official 
64
bribe
1000000 
next_official 
65
bribe
1000000 
next_official 
66
bribe
1000000 
next_official 
67
bribe
1000000 
next_official 
68
bribe
1000000 
next_official 
69
bribe
1000000 
next_official 
70
bribe
1000000 
next_official 
71
bribe
1000000 
next_official 
72
bribe
1000000 
next_official 
73
bribe
1000000 
next_official 
74
bribe
1000000 
next_official 
75
bribe
1000000 
next_official 
76
bribe
1000000 
next_official 
77
bribe
1000000 
next_official 
78
bribe
1000000 
next_official 
79
bribe
1000000 
next_official 
80
bribe
1000000 
next_official 
81
bribe
1000000 
next_official 
82
bribe
1000000 
next_official 
83
bribe
1000000 
next_official 
84
bribe
1000000 
next_official 
85
bribe
1000000 
next_official 
86
bribe
1000000 
next_official 
87
bribe
1000000 
next_official 
88
bribe
1000000 
next_official 
89
bribe
1000000 
next_official 
90
bribe
1000000 
next_official 
91
bribe
1000000 
next_official 
92
bribe
1000000 
next_official 
93
bribe
1000000 
next_official 
94
bribe
1000000 
next_official 
95
bribe
1000000 
next_official 
96
bribe
1000000 
next_official 
97
bribe
1000000 
next_official 
98
bribe
1000000 
next_official 
99
bribe
1000000 
next_official 
100
bribe
1000000 
next_official
stdout 
99000000
100/99/98/97/96/95/94/93/92/91/90/89/88/87/86/85/84/83/82/81/80/79/78/77/76/75/74/73/72/71/70/69/68/67/66/65/64/63/62/61/60/59/58/57/56/55/54/53/52/51/50/49/48/47/46/45/44/43/42/41/40/39/38/37/36/35/34/33/32/31/30/29/28/27/26/25/24/23/22/21/20/19/18/17/16/15/14/13/12/11/10/9/8/7/6/5/4/3/2/1
Working time: 17.477 ms
https://ideone.com/WwKRFp
AL16!!!!!
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!