Submission #626894

#	Time	Username	Problem	Language	Result	Execution time	Memory
626894		_L__	Bosses (BOI16_bosses)	C++17	100 / 100	648 ms	640 KiB

bosses

/**
    * Contest: Practice 
    * Date: 8/10/2022 
    * Start: 23:00 UTC+2
**/
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <type_traits>
#include <unordered_map>
 
using namespace std;
using namespace __gnu_pbds;
 
#define endl '\n'
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define double long double
#define F first
#define S second
const int N=5004,INF=1e17,MOD=1e9+7;
const double EPS=1e-10, PI=3.141592653589793238462643383279502;
 
template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;
 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
vector<int>D[N];
void do_work(int test_casesss){
int n;cin>>n;
for(int i=1;i<=n;++i){
int k;cin>>k;
for(int j=0;j<k;++j){
int x;cin>>x;
D[x].push_back(i);
}
}
int ANS=INF;
for(int i=1;i<=n;++i){
vector<int>USE(n+1,0);
queue<int>q;q.push(i);USE[i]=1;
int RET=0;
while(q.size()){
int x=q.front();q.pop();RET+=USE[x];
for(auto j:D[x])if(USE[j]==0){USE[j]=USE[x]+1;q.push(j);}
}
bool f=1;
for(int j=1;j<=n;++j)if(USE[j]==0){f=0;break;}
if(f==0)continue;
ANS=min(ANS,RET);
}
cout<<ANS<<endl;
}
 
int32_t main(){
//freopen("car.in","r",stdin);
//freopen("output1.txt","w",stdout);
fast;
do_work(1);
return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33