제출 #1008531

#제출 시각아이디문제언어결과실행 시간메모리
1008531AlmontherBosses (BOI16_bosses)C++98
0 / 100
1 ms728 KiB
#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; while(q.size()){ ll idx=q.front(); q.pop(); for(auto i:v[idx]){ if(vis[i]) continue; v1[idx].push_back(i); vis[i]=1; q.push(i); } } return dfs(x,0).second; } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...