Submission #439367

#	Time	Username	Problem	Language	Result	Execution time	Memory
439367		urosk	Bosses (BOI16_bosses)	C++14	100 / 100	1401 ms	144716 KiB

bosses

///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 int
#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;
    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;
        c[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<<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 (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:14:15: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   14 | #define llinf 100000000000000000LL // 10^17
      |               ^~~~~~~~~~~~~~~~~~~~
bosses.cpp:61:14: note: in expansion of macro 'llinf'
   61 |     ll ans = llinf;
      |              ^~~~~
bosses.cpp: In function 'void setIO(std::string)':
bosses.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:33:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33