| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1085860 | Izzy | Bosses (BOI16_bosses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int n;
unordered_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;
}