# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
439349 | 2021-06-29T17:00:38 Z | urosk | Bosses (BOI16_bosses) | C++14 | 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]; void dfs(ll u){ vis[u] = 1; ll ans = 0; if(sz(v[u])==0){ c[u] = k; return; } for(ll s : v[u]){ if(vis[s]) continue; dfs(s); ans+=c[s]; } c[u] = ans+k; } 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; if(h!=n) continue; fill(vis,vis+n+1,0); ll ans2 = 0; for(ll i = 1;i<=n;i++){ ans2+=c[i]; } ans = min(ans,ans2); } cout<<ans+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
# | 결과 | 실행 시간 | 메모리 | 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | - |