oj.uz

Submission #439365

# Submission time Handle Problem Language Result Execution time Memory
439365 2021-06-29T17:25:23 Z urosk Bosses (BOI16_bosses) C++14
67 / 100
 1323 ms 262148 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;
    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 '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 640 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 640 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 1 ms 716 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 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 1 ms 716 KB Output is correct
12 Correct 6 ms 1356 KB Output is correct
13 Correct 5 ms 1228 KB Output is correct
14 Correct 290 ms 77676 KB Output is correct
15 Correct 13 ms 1484 KB Output is correct
16 Correct 1020 ms 172792 KB Output is correct
17 Runtime error 1323 ms 262148 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -