제출 #91973

#제출 시각아이디문제언어결과실행 시간메모리
91973KamisamaBosses (BOI16_bosses)C++14
67 / 100
1574 ms764 KiB
#include <iostream> #include <cstdio> #include <vector> using namespace std; const int maxn=5e3+7; int n,h[maxn],res; vector<int> adj[maxn]; struct Queue{ unsigned sz; struct Node{ int val; Node *link; }*head,*tail; Queue():sz{0},head{nullptr},tail{nullptr}{}; inline bool Empty(){return head==nullptr;} inline void Push(const int &val){ Node *newTail=new Node; newTail->val=val; newTail->link=nullptr; if(tail) tail->link=newTail; tail=newTail; if(!head) head=tail; sz++; } inline int Pop(){ if(Empty()) return -1; Node *ptr=head; head=ptr->link; if(!head) tail=nullptr; int val=ptr->val; delete ptr; sz--; return val; } }; inline void Bfs(const int &root){ Queue q; fill(h,h+n+1,0); h[root]=1; int sum=1,nEdges=0; q.Push(root); while(!q.Empty()){ int u=q.Pop(); for(int v: adj[u]){ if(h[v]) continue; nEdges++; h[v]=h[u]+1; sum+=h[v]; q.Push(v); } } if(nEdges==n-1) res=min(res,sum); } inline void Read(int &x){ register char c; for(c=getchar();c>'9'||c<'0';c=getchar()); for(x=0;'0'<=c&&c<='9';c=getchar()) x=10*x+c-'0'; } inline void Write(const int &x){ if(x>9) Write(x/10); putchar(x%10+'0'); } int main(){ Read(n); for(int i=1,k=0;i<=n;i++){ Read(k); for(int j=1,x=0;j<=k;j++) cin>>x, adj[x].push_back(i); } res=(int)1e9+7; for(int i=1;i<=n;i++) Bfs(i); Write(res); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...