oj.uz

Submission #532606

# Submission time Handle Problem Language Result Execution time Memory
532606 2022-03-03T10:33:27 Z kebine Bosses (BOI16_bosses) C++17
100 / 100
 632 ms 612 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef double db;
#define pairll pair<ll,ll>
#define lpairll pair<pairll,ll>
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define repp(i,a,b) for(ll i = (a); i <= (b); i++)
#define repm(i, a, b) for (ll i = (a); i >= (b); i--)
#define repz(i, a, b) for (ll i = (a); i < (b); i++)
 
const long long MOD = 1e9+7, N = 5e3 + 5, Q = 4e3+5;

ll tc = 1, n, m,k, vis[N], tim = 0, tot = 0, sum = 0;
string s, ye = "YES", no = "NO", nu;
vector<ll> ED[N];

void fastt(){  
  ios_base::sync_with_stdio(0); 
  cin.tie(NULL);
  cout.tie(NULL);  
}

ll dfs(ll idx){
  if(vis[idx] == tim) return 0;
  vis[idx] = tim;
  tot++;
  ll maxd = 0;
  for (auto i : ED[idx]){
    if (vis[i] != tim) maxd += dfs(i);
  }
  //cout << idx << " " << 1+maxd << endl;
  sum += 1+maxd;
  return 1+maxd;  
}

void input(){
  cin >> n;
  repp(i,1,n){
    cin >> m;
    repp(j,1,m) cin >> k, ED[k].pb(i);
  }
} 

void solve(){
  ll ans = 1e18;
  repp(i,1,n){
    repp(j,1,n) vis[j] = -1;
    vis[i] = 1;
    queue<ll> q;
    q.push(i);
    tot = 1;
    sum = 1;
    while(!q.empty()){
      ll tt = q.front();
      q.pop();
      for (auto j : ED[tt]){
        if(vis[j] != -1) continue;
        vis[j] = vis[tt]+1;
        sum += vis[j];
        tot++;
        q.push(j); 
      }
    }
    if(tot != n) continue;
    ans = min(ans,sum);
  }
  cout << ans << endl;
}

int main(){
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  fastt();
  while(tc--){
    input();
    solve();
  }
}

/*

*/

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 112 ms 536 KB Output is correct
15 Correct 6 ms 492 KB Output is correct
16 Correct 475 ms 588 KB Output is correct
17 Correct 632 ms 612 KB Output is correct
18 Correct 631 ms 612 KB Output is correct