#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector <int> adj[5001];
int dp[5001] = {};
int d = 0;
bool vis[5001];
vector <int> newadj[5001];
void calc (int pos) {
dp[pos] = 1;
d++;
for (auto j : newadj[pos]) {
calc(j);
dp[pos] += dp[j];
}
}
signed main () {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
while (x--) {
int y;
cin >> y;
adj[y].push_back(i);
}
}
int ans = 1e9;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[j] = 0;
vis[j] = 0;
newadj[j].clear();
}
queue <int> cur;
cur.push(i);
vis[i] = 1;
while (!cur.empty()) {
int l = cur.front();
cur.pop();
for (auto j : adj[l]) {
if (!vis[j]) {
vis[j] = 1;
newadj[l].push_back(j);
cur.push(j);
}
}
}
d = 0;
calc(i);
if (d != n) continue;
int y = 0;
for (int j = 1; j <= n; j++) {
y += dp[j];
}
if (ans > y) ans = y;
}
cout << ans << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
680 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
680 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
680 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
5 ms |
772 KB |
Output is correct |
13 |
Correct |
4 ms |
796 KB |
Output is correct |
14 |
Correct |
223 ms |
1024 KB |
Output is correct |
15 |
Correct |
30 ms |
928 KB |
Output is correct |
16 |
Correct |
807 ms |
1116 KB |
Output is correct |
17 |
Correct |
844 ms |
1080 KB |
Output is correct |
18 |
Correct |
817 ms |
1080 KB |
Output is correct |