#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)
#define eb(x...) emplace_back(x)
template<class T> bool ckmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
constexpr int N = 10 << 9, inf = 1e9;
int n, ans[N];
vector<int> g[N], gt[N];
void dfs(int u, int p) {
trav(v, gt[u]) {
if (v == p) continue;
dfs(v, u);
ans[u] += ans[v];
}
}
int solve(int s) {
rep(u, 0, n) gt[u].clear();
vector<bool> vis(n);
queue<int> q; q.push(s);
vis[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
trav(v, g[u]) {
if (vis[v]) continue;
gt[u].eb(v);
q.push(v);
vis[v] = true;
}
}
rep(u, 0, n) if (!vis[u]) return inf;
rep(u, 0, n) ans[u] = 1;
dfs(s, s);
int ret = 0;
rep(u, 0, n) ret += ans[u];
return ret;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
rep(u, 0, n) {
int k; cin >> k;
rep(i, 0, k) {
int v; cin >> v; --v;
g[v].eb(u);
}
}
int ans = inf;
rep(u, 0, n) ckmin(ans, solve(u));
cout << ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
640 KB |
Output is correct |
3 |
Correct |
5 ms |
640 KB |
Output is correct |
4 |
Correct |
5 ms |
640 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
640 KB |
Output is correct |
3 |
Correct |
5 ms |
640 KB |
Output is correct |
4 |
Correct |
5 ms |
640 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
640 KB |
Output is correct |
7 |
Correct |
5 ms |
640 KB |
Output is correct |
8 |
Correct |
5 ms |
640 KB |
Output is correct |
9 |
Correct |
5 ms |
640 KB |
Output is correct |
10 |
Correct |
5 ms |
640 KB |
Output is correct |
11 |
Correct |
6 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
640 KB |
Output is correct |
3 |
Correct |
5 ms |
640 KB |
Output is correct |
4 |
Correct |
5 ms |
640 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
640 KB |
Output is correct |
7 |
Correct |
5 ms |
640 KB |
Output is correct |
8 |
Correct |
5 ms |
640 KB |
Output is correct |
9 |
Correct |
5 ms |
640 KB |
Output is correct |
10 |
Correct |
5 ms |
640 KB |
Output is correct |
11 |
Correct |
6 ms |
640 KB |
Output is correct |
12 |
Correct |
10 ms |
768 KB |
Output is correct |
13 |
Correct |
10 ms |
768 KB |
Output is correct |
14 |
Correct |
183 ms |
888 KB |
Output is correct |
15 |
Correct |
24 ms |
768 KB |
Output is correct |
16 |
Correct |
677 ms |
1016 KB |
Output is correct |
17 |
Correct |
1455 ms |
1144 KB |
Output is correct |
18 |
Correct |
1455 ms |
1028 KB |
Output is correct |