# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
851183 | 2023-09-18T19:39:35 Z | antonio2006 | Bosses (BOI16_bosses) | C++14 | 1 ms | 344 KB |
#include <iostream> #include <vector> #include <queue> using namespace std; const int dim=5005; int n; bool viz[dim]; int t[dim],d[dim]; vector<int> w[dim]; void genarb(int nod){ for(int i=1;i<=n;i++){ viz[i]=0; t[i]=0; } queue<int> Q; viz[nod]=1; Q.push(nod); while(!Q.empty()){ int x=Q.front(); Q.pop(); for(int i=0;i<w[x].size();i++){ int u=w[x][i]; if(!viz[u]){ t[u]=x; viz[u]=1; Q.push(u); } } } } int calcsum(int nod){ for(int i=1;i<=n;i++){ d[i]=0; viz[i]=0; } viz[nod]=1; queue<int> Q; Q.push(nod); int s=0; while(!Q.empty()){ int x=Q.front(); Q.pop(); for(int i=1;i<=n;i++){ if(t[i]==x and !viz[i]){ viz[i]=1; Q.push(i); d[i]=d[x]+1; } } } for(int i=1;i<=n;i++){ s+=d[i]; } return s+n; } int main(){ cin>>n; for(int i=1;i<=n;i++){ int m; cin>>m; for(int j=1;j<=m;j++){ int x; cin>>x; w[x].push_back(i); } } int sol=1e9; for(int i=1;i<=n;i++){ genarb(i); sol=min(sol,calcsum(i)); } cout<<sol; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Incorrect | 1 ms | 344 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Incorrect | 1 ms | 344 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Incorrect | 1 ms | 344 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |