# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
438180 |
2021-06-27T17:48:17 Z |
Urvuk3 |
Bosses (BOI16_bosses) |
C++17 |
|
794 ms |
708 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=5005,INF=1e10 ;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define endl "\n"
#define PRINT(x) cout<<#x<<'-'<<x<<endl
ll n, m, k, q, l, r, x, y, z, res=INF, tmp=0;
string s,t;
vector<int> adj[MAXN];
ll dist[MAXN];
bool visited[MAXN];
ll bfs(int x){
queue<int> q;
dist[x]=1;
visited[x]=true;
q.push(x);
while(!q.empty()){
int s=q.front(); q.pop();
for(auto v:adj[s]){
if(visited[v]) continue;
visited[v]=true;
dist[v]=dist[s]+1;
q.push(v);
}
}
ll sum=0;
for(int i=1;i<=n;i++){
sum+=dist[i];
}
for(int i=1;i<=n;i++){
if(!visited[i]){
return INF;
}
}
return sum;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>q;
for(int j=0;j<q;j++){
cin>>x;
adj[x].push_back(i);
}
}
for(int i=1;i<=n;i++){
memset(visited,false,sizeof(visited));
memset(dist,0,sizeof(dist));
tmp=0;
res=min(res,bfs(i));
}
cout<<res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int t;
//cin>>t;
t=1;
while(t--){
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
436 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
436 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
436 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
6 ms |
588 KB |
Output is correct |
13 |
Correct |
5 ms |
504 KB |
Output is correct |
14 |
Correct |
161 ms |
588 KB |
Output is correct |
15 |
Correct |
35 ms |
588 KB |
Output is correct |
16 |
Correct |
596 ms |
660 KB |
Output is correct |
17 |
Correct |
783 ms |
680 KB |
Output is correct |
18 |
Correct |
794 ms |
708 KB |
Output is correct |