# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
488249 |
2021-11-18T10:03:16 Z |
DUONG |
Bosses (BOI16_bosses) |
C++14 |
|
633 ms |
656 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i --)
const int MAX=5003;
int vis[MAX],n,cnt=0;
ll cost=0;
vector< vector<int> >adj(MAX) ;
void bfs(int src)
{
queue<pair<int,int>>q ;
q.push({src,1}) ;
vis[src]=1 ;
while(!q.empty())
{
pair<int,int>p=q.front();
q.pop();
cnt++;
int node=p.first;
cost+=(p.second*1ll) ;
for(auto &child : adj[node])
{
if(vis[child]==1) continue;
vis[child]=1;
q.push({child,p.second+1}) ;
}
}
}
int main()
{
// freopen("BOSSES.INP","r",stdin);
// freopen("BOSSES.OUT","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
FOR(i,1,n)
{
int m;
cin>>m;
while(m--)
{
int x;
cin>>x;
adj[x].push_back(i);
}
}
ll ans=1e18;
FOR(i,1,n)
{
memset(vis,0,sizeof(vis));
cnt=0,cost=0;
bfs(i);
if(cnt!=n) continue;
ans=min(ans,cost);
}
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
464 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
464 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
464 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
3 ms |
580 KB |
Output is correct |
13 |
Correct |
2 ms |
592 KB |
Output is correct |
14 |
Correct |
128 ms |
452 KB |
Output is correct |
15 |
Correct |
4 ms |
464 KB |
Output is correct |
16 |
Correct |
473 ms |
656 KB |
Output is correct |
17 |
Correct |
631 ms |
652 KB |
Output is correct |
18 |
Correct |
633 ms |
592 KB |
Output is correct |