이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array
const int INF = 1e15;
const int MOD = 1e9+7;
const int MXN = 5005;
vector<int> g[MXN];
int n;
int bfs(int rt) {
vector<bool> vis(n, 0);
queue<int> q;
vector<ar<int,2>> ch[n];
q.push(rt);
vis[rt] = 1;
auto nextLayer = [&](int u) {
int lol = 0;
for (int v : g[u]) if (!vis[v]) lol++;
return lol;
};
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) if (!vis[v]) {
ch[u].push_back({-nextLayer(v), v});
vis[v] = 1;
}
sort(ch[u].begin(), ch[u].end());
for (auto v : ch[u]) q.push(v[1]);
}
int ans = 0;
function<int(int)> dfs = [&](int u) {
int cur = 1;
for (ar<int,2> v : ch[u]) {
cur += dfs(v[1]);
}
ans += cur;
return cur;
};
dfs(rt);
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for (int i = 0; i < n; i++) {
int x; cin>>x;
while (x--) {
int j; cin>>j; --j;
g[j].push_back(i);
}
}
int ans = INF;
for (int i = 0; i < n; i++) ans = min(ans, bfs(i));
cout<<ans<<"\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... |