제출 #813767

#제출 시각아이디문제언어결과실행 시간메모리
813767chanvcl123Bosses (BOI16_bosses)C++14
0 / 100
1 ms596 KiB
//#pragma gcc optimize("Ofast") //#pragma GCC optimization("Ofast") //#pragma optimize(Ofast) //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") //pragma xin // Judges with GCC >= 12 only needs Ofast // #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize") // MLE optimization // #pragma GCC optimize("conserve-stack") // Old judges // #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2") // New judges. Test with assert(__builtin_cpu_supports("avx2")); // #pragma GCC target("arch=skylake") // Atcoder // #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma" #include<bits/stdc++.h> #define F first #define Sc second #define pb push_back #define endl "\n" using namespace std; using ll=long long; ll n; vector<ll> adj[6005]; ll dp[6005]; vector<ll> g[6005]; ll cnt=0; ll sum=0; ll ans=1e18; queue<int> Q; void dfs(int u){ dp[u]=1; ++cnt; for (int v: g[u]){ dfs(v); dp[u]+=dp[v]; } sum+=dp[u]; } void bfs(int source){ sum=0; cnt=0; Q.push(source); bool visited[n+5]={}; visited[source]=1; while(!Q.empty()){ int u=Q.front(); Q.pop(); for(int v:adj[u]){ if(visited[v]) continue; visited[v]=true; Q.push(v); // cnt++; g[u].push_back(v); } } dfs(source); if(cnt==n){ ans=min(ans,sum); } } int main(){ // freopen("atlanin.txt", "r", stdin); // freopen("atlanout.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; int k; int x; for(int i=1;i<=n;++i){ cin>>k; for(int j=1;j<=k;++j){ cin>>x; adj[x].emplace_back(i); } } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j) { dp[j]=0; g[j].clear(); } bfs(i); ans=min(ans,sum); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...