# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
813370 | 2023-08-07T16:26:37 Z | SteGG | Bosses (BOI16_bosses) | C++17 | 1118 ms | 980 KB |
#include <bits/stdc++.h> #define int long long using namespace std; void open(){ if(fopen("input.inp", "r")){ freopen("input.inp", "r", stdin); // freopen("output.out", "w", stdout); } } const int inf = 3e18; const int maxn = 5005; int n; vector<int> candidate[maxn]; vector<int> tr[maxn]; bool check[maxn]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); open(); cin >> n; for(int i = 1; i <= n; i++){ int k; cin >> k; for(int j = 1; j <= k; j++){ int a; cin >> a; candidate[a].push_back(i); } } int result; int last_result = inf; auto dfs = [&](auto &&dfs, int u) -> int { int sz = 1; for(int v : tr[u]){ sz += dfs(dfs, v); } result += sz; return sz; }; for(int root = 1; root <= n; root++){ memset(check, false, sizeof(check)); for(int i = 0; i <= n; i++){ tr[i].clear(); } queue<pair<int, int>> q; q.push({root, 0}); int cnt = 0; while(!q.empty()){ int u = q.front().first; int p = q.front().second; q.pop(); if(check[u]) continue; cnt++; check[u] = true; tr[p].push_back(u); for(int v : candidate[u]){ if(check[v]) continue; q.push({v, u}); } } if(cnt < n) continue; result = 0; dfs(dfs, root); last_result = min(result, last_result); } cout << last_result << endl; 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 | 560 KB | Output is correct |
4 | Correct | 1 ms | 468 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 | 560 KB | Output is correct |
4 | Correct | 1 ms | 468 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 | 560 KB | Output is correct |
4 | Correct | 1 ms | 468 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 | 17 ms | 880 KB | Output is correct |
13 | Correct | 16 ms | 960 KB | Output is correct |
14 | Correct | 173 ms | 828 KB | Output is correct |
15 | Correct | 26 ms | 724 KB | Output is correct |
16 | Correct | 720 ms | 980 KB | Output is correct |
17 | Correct | 1118 ms | 940 KB | Output is correct |
18 | Correct | 1047 ms | 940 KB | Output is correct |