# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
368062 | 2021-02-19T12:15:15 Z | benedict0724 | Bosses (BOI16_bosses) | C++17 | 1247 ms | 888 KB |
#include <bits/stdc++.h> using namespace std; vector<int> adj[5001]; queue<int> q; bool visited[5001]; int dp[5001], parent[5001]; int n; int bfs(int x){ for(int i=1;i<=n;i++){ visited[i] = false; dp[i] = 0; } visited[x] = true; vector<int> seq; q.push(x); while(!q.empty()){ int now = q.front(); q.pop(); for(int i : adj[now]){ if(!visited[i]){ visited[i] = true; parent[i] = now; q.push(i); } } seq.push_back(now); } if(seq.size() != n) return 1e9; int sum = 0; for(int i=n-1;i>=0;i--){ dp[seq[i]] += 1; dp[parent[seq[i]]] += dp[seq[i]]; sum += dp[seq[i]]; } return sum; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i=1;i<=n;i++){ int k; cin >> k; for(int j=1;j<=k;j++){ int e; cin >> e; adj[e].push_back(i); } } int ans = 1e9; for(int i=1;i<=n;i++){ ans = min(ans, bfs(i)); } cout << ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 492 KB | Output is correct |
4 | Correct | 1 ms | 512 KB | Output is correct |
5 | Correct | 1 ms | 492 KB | Output is correct |
6 | Correct | 1 ms | 492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 492 KB | Output is correct |
4 | Correct | 1 ms | 512 KB | Output is correct |
5 | Correct | 1 ms | 492 KB | Output is correct |
6 | Correct | 1 ms | 492 KB | Output is correct |
7 | Correct | 1 ms | 492 KB | Output is correct |
8 | Correct | 1 ms | 492 KB | Output is correct |
9 | Correct | 1 ms | 492 KB | Output is correct |
10 | Correct | 1 ms | 492 KB | Output is correct |
11 | Correct | 1 ms | 492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 492 KB | Output is correct |
4 | Correct | 1 ms | 512 KB | Output is correct |
5 | Correct | 1 ms | 492 KB | Output is correct |
6 | Correct | 1 ms | 492 KB | Output is correct |
7 | Correct | 1 ms | 492 KB | Output is correct |
8 | Correct | 1 ms | 492 KB | Output is correct |
9 | Correct | 1 ms | 492 KB | Output is correct |
10 | Correct | 1 ms | 492 KB | Output is correct |
11 | Correct | 1 ms | 492 KB | Output is correct |
12 | Correct | 6 ms | 492 KB | Output is correct |
13 | Correct | 4 ms | 620 KB | Output is correct |
14 | Correct | 208 ms | 748 KB | Output is correct |
15 | Correct | 44 ms | 620 KB | Output is correct |
16 | Correct | 750 ms | 888 KB | Output is correct |
17 | Correct | 1226 ms | 776 KB | Output is correct |
18 | Correct | 1247 ms | 776 KB | Output is correct |