| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1084774 | 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;
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 < 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++;
if (pos == levels[lvl].size()) {
salary += levels[lvl].size() * (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 (i = 0; i < n; i++) {
if (arr.find(i) != arr.end()) {
int temp = test(i);
if (temp > salary) {
salary = temp;
}
}
}
cout << salary;
}