# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
626892 |
2022-08-11T23:28:12 Z |
_L__ |
Bosses (BOI16_bosses) |
C++17 |
|
622 ms |
716 KB |
/**
* Contest: Practice
* Date: 8/10/2022
* Start: 23:00 UTC+2
**/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <type_traits>
#include <unordered_map>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define double long double
#define F first
#define S second
const int N=5004,INF=1e17,MOD=1e9+7;
const double EPS=1e-10, PI=3.141592653589793238462643383279502;
template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
vector<int>D[N];
void do_work(int test_casesss){
int n;cin>>n;
for(int i=1;i<=n;++i){
int k;cin>>k;
for(int j=0;j<k;++j){
int x;cin>>x;
D[x].push_back(i);
}
}
int ANS=INF;
for(int i=1;i<=n;++i){
vector<int>USE(n+1,INF);
queue<int>q;q.push(i);USE[i]=1;
int RET=0;
while(q.size()){
int x=q.front();q.pop();RET+=USE[x];
for(auto j:D[x])if(USE[j]==INF){USE[j]=USE[x]+1;q.push(j);}
}
bool f=1;
for(int j=1;j<=n;++j)if(USE[j]==INF){f=0;break;}
if(f==0)continue;
ANS=min(ANS,RET);
}
cout<<ANS<<endl;
}
int32_t main(){
//freopen("car.in","r",stdin);
//freopen("output1.txt","w",stdout);
fast;
do_work(1);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
440 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
440 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
440 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
4 ms |
524 KB |
Output is correct |
13 |
Correct |
3 ms |
576 KB |
Output is correct |
14 |
Correct |
128 ms |
596 KB |
Output is correct |
15 |
Correct |
7 ms |
596 KB |
Output is correct |
16 |
Correct |
477 ms |
696 KB |
Output is correct |
17 |
Correct |
605 ms |
716 KB |
Output is correct |
18 |
Correct |
622 ms |
684 KB |
Output is correct |