제출 #1085267

#제출 시각아이디문제언어결과실행 시간메모리
1085267IzzyBosses (BOI16_bosses)C++14
67 / 100
1561 ms932 KiB
#include <vector> #include <algorithm> #include <iostream> #include <map> using namespace std; int n; map<int, vector<int>> arr; int test(int start) { vector<bool> visited(n, false); vector<vector<int>> levels = {{start}}; int lvl = 0; int pos = 0; int salary = 0; visited[start] = true; while (lvl < int(levels.size())) { 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 (int(levels.size()) > lvl + 1) { levels[lvl + 1].push_back(i); } else { levels.push_back({i}); } } } } pos++; int a = int(levels[lvl].size()); if (pos == a) { salary += a * (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...