Submission #626882

#	Time	Username	Problem	Language	Result	Execution time	Memory
626882		_L__	Bosses (BOI16_bosses)	C++17	0 / 100	152 ms	262144 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>G[N],D[N];
int DP[N];
void dfs(int nde){
DP[nde]=1;
for(auto i: G[nde]){
dfs(i);
DP[nde]+=DP[i];
}
return;
}
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){
int USE[n+1]={};USE[i]=1;
queue<int>q;q.push(i);
while(q.size()){
int x=q.front();q.pop();
for(auto j:D[x])if(!(USE[j])){G[x].push_back(j);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;
dfs(i);
int B=0; for(int j=1;j<=n;++j)B+=DP[j];
for(int j=0;j<=n;++j)G[j].clear(),DP[j]=0;
ANS=min(ANS,B);
}
cout<<ANS<<endl;
}
 
int32_t main(){
//freopen("car.in","r",stdin);
//freopen("output1.txt","w",stdout);
fast;
do_work(1);
return 0;
}

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