This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |