# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
695227 | 2023-02-04T20:03:30 Z | Abito | Bosses (BOI16_bosses) | C++14 | 720 ms | 748 KB |
#include <bits/stdc++.h> using namespace std; #define pb push_back #define F first #define S second #define int long long #define ep insert const int N=5005; int n,p[N],dp[N]; vector<int> adj[N]; vector<int> q; void bfs(int node){ q.pb(node); for (int i=0;i<q.size();i++){ for (auto u:adj[q[i]]){ if (p[u]) continue; p[u]=q[i]; q.pb(u); } }return; } void getans(){ reverse(q.begin(),q.end()); for (int i=0;i<q.size()-1;i++) dp[p[q[i]]]+=dp[q[i]]; return; } int32_t main(){ cin>>n; for (int i=1;i<=n;i++){ int x;cin>>x; while (x--){ int y;cin>>y; adj[y].pb(i); } } int ans=INT_MAX; for (int i=1;i<=n;i++){ q.clear(); for (int i=1;i<=n;i++){ p[i]=0; dp[i]=1; }p[i]=-1; bfs(i); if (q.size()<n) continue; getans(); int s=0; for (int i=1;i<=n;i++) s+=dp[i]; ans=min(ans,s); }cout<<ans<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 5 ms | 468 KB | Output is correct |
13 | Correct | 4 ms | 596 KB | Output is correct |
14 | Correct | 101 ms | 676 KB | Output is correct |
15 | Correct | 19 ms | 740 KB | Output is correct |
16 | Correct | 457 ms | 748 KB | Output is correct |
17 | Correct | 720 ms | 744 KB | Output is correct |
18 | Correct | 719 ms | 740 KB | Output is correct |