제출 #1085277

#제출 시각아이디문제언어결과실행 시간메모리
1085277IzzyBosses (BOI16_bosses)C++14
67 / 100
1596 ms972 KiB
#include <vector> #include <algorithm> #include <iostream> #include <map> using namespace std; int n; map<int, vector<int>> arr; int test(int start) { int lvlCount = 1; // int posCount = 1; vector<bool> visited(n, false); vector<vector<int>> levels = {{start}}; int lvl = 0; int pos = 0; int salary = 0; vector<int> posLen = {1}; visited[start] = true; while (lvl < lvlCount) { start = levels[lvl][pos]; auto it = arr.find(start); if (it != arr.end()) { for (int i: arr[start]) { if (!visited[i]) { visited[i] = true; if (lvlCount > lvl + 1) { levels[lvl + 1].push_back(i); posLen[lvl + 1]++; } else { levels.push_back({i}); lvlCount++; posLen.push_back(1); } } } } pos++; // int a = int(levels[lvl].size()); if (pos == posLen[lvl]) { salary += posLen[lvl] * (lvl + 1); lvl++; pos = 0; } } if (find(visited.begin(), visited.end(), false) == visited.end()) { return salary; } return 2147483646; } int main() { int salary = 2147483646; cin >> n; for (int i = 0; i < n; i++) { int len; cin >> len; vector<int> temp; for (int j = 0; j < len; j++) { int x; cin >> x; x--; if (arr.find(x) == arr.end()) { arr[x] = {i}; } else { arr[x].push_back(i); } } } for (int i = 0; i < n; i++) { if (arr.find(i) != arr.end()) { int temp = test(i); if (temp < salary) { salary = temp; } } } cout << salary; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...