# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1008539 |
2024-06-26T14:11:30 Z |
vjudge1 |
Bosses (BOI16_bosses) |
C++17 |
|
1076 ms |
1108 KB |
#include <bits/stdc++.h>
#define suiii ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define co cout<<
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,sse3,sse4,avx")
using namespace std;
//stuff
vector<ll>v[5005],v1[5005];
ll n;
pair<ll,ll>dfs(ll x,ll last){
ll ans=1;
ll ans1=0;
for(auto i:v1[x]){
if(i==last) continue;
pair<ll,ll>a=dfs(i,x);
ans+=a.first;
ans1+=a.second;
}
ans1+=ans;
return {ans,ans1};
}
ll bfs(ll x){
ll vis[5005]={};
for(int i=0;i<=n;i++) v1[i].clear();
queue<ll>q;
q.push(x);
vis[x]=1;
ll cnt=1;
while(q.size()){
ll idx=q.front();
q.pop();
for(auto i:v[idx]){
if(vis[i]) continue;
v1[idx].push_back(i);
cnt++;
vis[i]=1;
q.push(i);
}
}
if(cnt==n) return dfs(x,0).second;
return 1e18;
}
void solve(){
cin>>n;
ll ans=1e18;
for(int i=1;i<=n;i++){
ll k;
cin>>k;
for(int j=0;j<k;j++){
ll b;
cin>>b;
v[b].push_back(i);
}
}
for(int i=1;i<=n;i++){
ans=min(ans,bfs(i));
}
co ans;
}
int main()
{
suiii
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
3 ms |
856 KB |
Output is correct |
13 |
Correct |
2 ms |
860 KB |
Output is correct |
14 |
Correct |
137 ms |
900 KB |
Output is correct |
15 |
Correct |
29 ms |
856 KB |
Output is correct |
16 |
Correct |
584 ms |
1048 KB |
Output is correct |
17 |
Correct |
978 ms |
1104 KB |
Output is correct |
18 |
Correct |
1076 ms |
1108 KB |
Output is correct |