| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 439358 | 2021-06-29T17:21:53 Z | urosk | Bosses (BOI16_bosses) | C++ | 1 ms | 588 KB |
///sat
#include <chrono>
using namespace std::chrono;
#define vremestart auto start = high_resolution_clock::now();
#define vremeend auto stop = high_resolution_clock::now();
#define vremeispis auto duration = duration_cast<microseconds>(stop - start); cout << duration.count() << endl;
///sat
#define here cerr<<"---------------------------\n"
#define popcount(x) __builtin_popcount(x) ///broj bitova
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define th third
#define fo fourth
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
using namespace std;
void setIO(string inoutname)
{
freopen((inoutname+".in").c_str(),"r",stdin);
freopen((inoutname+".out").c_str(),"w",stdout);
}
ll gcd(ll a, ll b)
{
if(b==0) return a;
if(a==0) return b;
if(a>=b) return gcd(a%b,b);
return gcd(a,b%a);
}
#define maxn 5005
ll n,k;
vector<ll> g[maxn];
vector<ll> a[maxn];
vector<ll> v[maxn];
bool vis[maxn];
ll c[maxn];
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> k;
for(ll i = 1;i<=n;i++){
ll m; cin >> m;
for(ll j = 1;j<=m;j++){
ll x; cin >> x;
g[x].pb(i);
a[i].pb(x);
}
}
ll ans = llinf;
for(ll i = 1;i<=n;i++){
queue<ll> q;
q.push(i);
fill(vis,vis+n+1,0);
fill(c,c+n+1,0);
ll h = 0;
vis[i] = 1;
while(!q.empty()){
ll u = q.front();
h++;
q.pop();
for(ll s : g[u]){
if(vis[s]) continue;
v[u].pb(s);
vis[s] = 1;
q.push(s);
c[s] = c[u]+1;
}
}
//cerr<<h<<endl;
ll ans2 = 0;
for(ll i = 1;i<=n;i++){
ans2+=c[i];
if(vis[i]==0) goto lol;
}
ans = min(ans,ans2);
lol:;
}
cout<<ans*k+n*k<<endl;
return 0;
}
/*
100 256
3 50 11 85
2 84 69
2 41 39
2 43 82
2 49 26
2 48 47
2 36 65
2 37 41
2 73 100
1 40
2 20 98
2 46 31
2 29 22
2 99 52
2 50 27
1 45
2 28 44
2 83 60
3 76 93 35
2 11 58
2 78 76
3 49 90 63
1 16
2 34 52
2 49 60
2 5 58
2 92 34
2 43 55
2 90 22
2 71 7
2 87 37
2 82 84
3 85 43 38
2 19 21
2 27 24
2 95 33
2 12 51
2 73 42
2 3 61
2 69 25
2 51 3
2 59 65
2 56 75
2 89 55
1 18
2 95 87
2 71 97
2 75 97
2 5 25
2 92 54
3 72 45 31
2 93 40
2 89 78
2 59 96
2 17 71
2 64 14
2 94 100
2 26 20
2 15 1
2 13 83
2 98 39
2 53 44
2 72 6
2 67 30
2 33 1
2 36 46
2 73 28
1 88
1 2
2 53 21
2 94 8
2 47 80
2 43 74
2 77 56
2 79 64
2 24 70
2 14 10
2 62 70
2 30 57
2 6 81
3 9 48 84
1 4
2 29 13
1 32
2 42 54
3 77 72 52
2 12 66
1 23
2 62 17
2 63 80
2 57 9
2 19 96
2 91 81
4 67 86 60 52
2 38 66
2 15 35
2 79 91
2 61 11
2 26 68
2 86 74
*/
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 588 KB | Output is correct |
| 2 | Incorrect | 1 ms | 588 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 588 KB | Output is correct |
| 2 | Incorrect | 1 ms | 588 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 588 KB | Output is correct |
| 2 | Incorrect | 1 ms | 588 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |