# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1209054 | badge881 | Bosses (BOI16_bosses) | C++20 | 772 ms | 1012 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> baseListAdj, listAdj;
pair<int, int> dfs(int x)
{
int ans = 0, sm = 1;
for (auto v : listAdj[x])
{
auto [ansi, smi] = dfs(v);
ans += ansi, sm += smi;
}
ans += sm;
return {ans, sm};
}
signed main()
{
int n;
scanf("%d", &n);
baseListAdj.resize(n), listAdj.resize(n);
vector<int> cnt(n);
for (int i = 0; i < n; i++)
{
int k;
scanf("%d", &k);
for (int j = 0; j < k; j++)
{
int x;
scanf("%d", &x);
x--;
baseListAdj[x].push_back(i);
}
}
int ans = n * n;
for (int t = 0; t < n; t++)
{
queue<int> q;
q.push(t);
vector<int> dist(n, 0);
vector<bool> visited(n, 0);
visited[t] = 1;
for (auto &u : listAdj)
u.clear();
while (!q.empty())
{
int u = q.front();
q.pop();
for (auto v : baseListAdj[u])
if (!visited[v])
{
dist[v] = dist[u] + 1, visited[v] = 1;
q.push(v);
listAdj[u].push_back(v);
}
}
bool ok = 1;
for (int i = 0; i < n; i++)
if (!visited[i])
ok = 0;
if (!ok)
continue;
ans = min(ans, dfs(t).first);
}
printf("%d\n", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |