oj.uz

Submission #439367

# Submission time Handle Problem Language Result Execution time Memory
439367 2021-06-29T17:27:11 Z urosk Bosses (BOI16_bosses) C++14
100 / 100
 1401 ms 144716 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 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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 6 ms 972 KB Output is correct
13 Correct 5 ms 972 KB Output is correct
14 Correct 280 ms 40412 KB Output is correct
15 Correct 11 ms 1100 KB Output is correct
16 Correct 953 ms 90080 KB Output is correct
17 Correct 1398 ms 142988 KB Output is correct
18 Correct 1401 ms 144716 KB Output is correct