#include "bits/stdc++.h"
using namespace std;
const int MAXN = 5005;
vector< vector<int> > adj(MAXN), rev(MAXN);
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
int amount;
cin >> amount;
while(amount--)
{
int f;
cin >> f;
adj[i].push_back(f);
rev[f].push_back(i);
}
}
queue<int> q;
long long res = 1e18;
for(int i = 1; i <= n; i++)
{
vector<bool> visited(n+5);
vector<int> indeg(n+5);
vector<long long> ans(n+5);
vector<int> par(n+5, 1e9);
visited[i] = true;
par[i] = -1;
queue<int> q;
q.push(i);
while(!q.empty())
{
int v = q.front();
q.pop();
for(int e : rev[v])
{
if(visited[e])
continue;
visited[e] = true;
par[e] = v;
indeg[v]++;
q.push(e);
}
}
for(int idx = 1; idx <= n; idx++)
{
if(indeg[idx] == 0)
q.push(idx);
}
long long temp = 0;
while(!q.empty())
{
int v = q.front();
q.pop();
ans[v]++;
temp += ans[v];
if(par[v] != -1 && par[v] != 1e9)
{
indeg[par[v]]--;
ans[par[v]] += ans[v];
if(indeg[par[v]] == 0)
q.push(par[v]);
}
}
for(int i = 1; i <= n; i++)
{
if(par[i] == 1e9) // There is an element which isn't in the hierarchy
temp = 1e18;
}
res = min(res, temp);
}
cout << res << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
540 KB |
Output is correct |
8 |
Correct |
1 ms |
532 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
536 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
540 KB |
Output is correct |
8 |
Correct |
1 ms |
532 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
536 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
7 ms |
596 KB |
Output is correct |
13 |
Correct |
5 ms |
676 KB |
Output is correct |
14 |
Correct |
489 ms |
884 KB |
Output is correct |
15 |
Correct |
238 ms |
884 KB |
Output is correct |
16 |
Correct |
1056 ms |
980 KB |
Output is correct |
17 |
Correct |
1303 ms |
980 KB |
Output is correct |
18 |
Correct |
1310 ms |
980 KB |
Output is correct |