#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int N, K;
vector<int> adj[5005];
bool ok[5005];
int topo[5005], par[5005], pos[5005];
int p;
long long sz[5005];
long long ans = LLONG_MAX;
void solve(int rt) {
p = N - 1;
queue<pii> q;
memset(ok, 0, sizeof(ok));
ok[rt] = 1;
for(int v : adj[rt]) q.emplace(v, rt);
topo[N] = rt;
par[rt] = 0;
int u;
while(!q.empty()) {
u = q.front().first;
if(ok[u] == 0) {
ok[u] = 1;
topo[p] = u, pos[u] = p;
par[u] = q.front().second;
for(int v : adj[u]) {
q.emplace(v, u);
}
p--;
}
q.pop();
}
if(p) return;
memset(sz, 0, sizeof(sz));
long long res = 0;
// cout << rt << ":\n";
for(int i = 1; i <= N; i++) {
u = topo[i];
// cout << u << " " << par[u] << "\n";
sz[u]++;
res += sz[u];
sz[par[u]] += sz[u];
}
ans = min(ans, res);
}
int main() {
ios_base::sync_with_stdio(0);
cin >> N;
int u;
for(int i = 1; i <= N; i++) {
cin >> K;
while(K--) {
cin >> u;
adj[u].emplace_back(i);
}
}
for(int i = 1; i <= N; i++) solve(i);
cout << ans << "\n";
cin >> N;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
0 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
0 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
0 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
19 ms |
640 KB |
Output is correct |
13 |
Correct |
15 ms |
640 KB |
Output is correct |
14 |
Correct |
145 ms |
720 KB |
Output is correct |
15 |
Correct |
4 ms |
640 KB |
Output is correct |
16 |
Correct |
696 ms |
908 KB |
Output is correct |
17 |
Correct |
972 ms |
832 KB |
Output is correct |
18 |
Correct |
997 ms |
832 KB |
Output is correct |