oj.uz

Submission #813288

# Submission time Handle Problem Language Result Execution time Memory
813288 2023-08-07T15:03:48 Z trucmai Bosses (BOI16_bosses) C++17
100 / 100
 476 ms 24068 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
  #include "/home/trucmai/.vim/tools.h"
  #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
  #else
  #define debug(x...)
#endif

void open(){
  if(fopen("i.inp","r")){
    freopen("i.inp","r",stdin);
    freopen("o.out","w",stdout);
  }
}

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "

const int MN = 1e6 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;
ll n; vector<ll>g[MN];
ll bfs(ll root){
  queue<ll>qu; ll res = 0;
  vector<ll>h(n+1,0); vector<bool>vis(n+1,false); 
  h[root] = 1; qu.push(root); vis[root] = true; 
  while(!qu.empty()){
    ll u = qu.front(); qu.pop();
    res += h[u]; 
    for(ll &v : g[u]){
      if(vis[v]) continue; 
      h[v] = h[u] + 1; 
      vis[v] = true;
      qu.push(v);
    }
  }
  bool flag = true; 
  for(ll i = 1;i <= n;++i) flag &= vis[i]; 
  return (flag ? res : INF);
}
void solve(){
  cin>>n; 
  for(ll i = 1;i <= n;++i){
    ll k; cin>>k; 
    for(ll j = 1;j <= k;++j){
      ll x; cin>>x; 
      g[x].push_back(i);
    }
  }
  ll res = INF;
  for(ll r = 1;r <= n;++r) res = min(res,bfs(r));
  cout<<res<<endl;
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);
  open();
  ll t = 1; //cin>>t;
  while(t--) solve(); 
  
  #ifdef LOCAL
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  #endif
}

Compilation message

bosses.cpp: In function 'void open()':
bosses.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen("i.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
bosses.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("o.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23800 KB Output is correct
3 Correct 13 ms 23808 KB Output is correct
4 Correct 13 ms 23808 KB Output is correct
5 Correct 11 ms 23808 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23800 KB Output is correct
3 Correct 13 ms 23808 KB Output is correct
4 Correct 13 ms 23808 KB Output is correct
5 Correct 11 ms 23808 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23776 KB Output is correct
8 Correct 11 ms 23804 KB Output is correct
9 Correct 11 ms 23688 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct
11 Correct 12 ms 23804 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23800 KB Output is correct
3 Correct 13 ms 23808 KB Output is correct
4 Correct 13 ms 23808 KB Output is correct
5 Correct 11 ms 23808 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23776 KB Output is correct
8 Correct 11 ms 23804 KB Output is correct
9 Correct 11 ms 23688 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct
11 Correct 12 ms 23804 KB Output is correct
12 Correct 15 ms 23892 KB Output is correct
13 Correct 14 ms 23892 KB Output is correct
14 Correct 109 ms 23892 KB Output is correct
15 Correct 38 ms 23960 KB Output is correct
16 Correct 437 ms 24068 KB Output is correct
17 Correct 476 ms 24052 KB Output is correct
18 Correct 458 ms 24052 KB Output is correct