# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
546121 | 2022-04-06T12:06:29 Z | Hanksburger | Bosses (BOI16_bosses) | C++17 | 1392 ms | 984 KB |
#include <bits/stdc++.h> using namespace std; vector<long long> adj[5005], child[5005]; bool visited[5005]; queue<long long> q; long long a[5005]; void dfs(long long u) { long long sum=0; for (long long i=0; i<child[u].size(); i++) { long long v=child[u][i]; dfs(v); sum+=a[v]; } a[u]=sum+1; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long n, ans=1e18; cin >> n; for (long long i=1; i<=n; i++) { long long x; cin >> x; for (long long j=1; j<=x; j++) { long long u; cin >> u; adj[u].push_back(i); } } for (long long i=1; i<=n; i++) { for (long long j=1; j<=n; j++) { child[j].clear(); visited[j]=0; } visited[i]=1; q.push(i); while (!q.empty()) { long long u=q.front(); q.pop(); for (long long j=0; j<adj[u].size(); j++) { long long v=adj[u][j]; if (!visited[v]) { child[u].push_back(v); visited[v]=1; q.push(v); } } } bool ok=1; for (long long j=1; j<=n; j++) { if (!visited[j]) { ok=0; break; } } if (ok) { dfs(i); long long sum=0; for (long long j=1; j<=n; j++) sum+=a[j]; ans=min(ans, sum); } } cout << ans; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 1 ms | 564 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 1 ms | 564 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 1 ms | 564 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
12 | Correct | 5 ms | 776 KB | Output is correct |
13 | Correct | 4 ms | 852 KB | Output is correct |
14 | Correct | 218 ms | 904 KB | Output is correct |
15 | Correct | 24 ms | 800 KB | Output is correct |
16 | Correct | 764 ms | 956 KB | Output is correct |
17 | Correct | 1364 ms | 980 KB | Output is correct |
18 | Correct | 1392 ms | 984 KB | Output is correct |