oj.uz

Submission #790740

# Submission time Handle Problem Language Result Execution time Memory
790740 2023-07-23T07:21:25 Z christinelynn Bosses (BOI16_bosses) C++17
100 / 100
 428 ms 5324 KB 
#include<bits/stdc++.h>

#define pb push_back
#define int long long
#define INF 1e18
#define endl '\n'
 
using namespace std;

int n , k , ans = 1e18 , dist[200005];
vector < int > adj[200005];
bool vis[200005];

void bfs(int s){
  queue < int > q;
  vis[s] = true;
  q.push(s);
  dist[s] = 1;
  int ttl = 1;
  while(!q.empty()){
    int u = q.front(); q.pop();
    for(int i : adj[u]){
      if(!vis[i]){
        vis[i] = true;
        q.push(i);
        dist[i] = dist[u] + 1;
        ttl += dist[i];
      }
    }
  }
  bool bs = true;
  for(int i = 1 ; i <= n ; i++) if(!vis[i]) bs = false;
  if(bs) ans = min(ans , ttl);
}

signed main(){
  cin >> n;
  for(int i = 1 ; i <= n ; i++){
    cin >> k;
    for(int j = 1 ; j <= k ; j++){
      int tmp; cin >> tmp;
      adj[tmp].pb(i);
    }
  }
  for(int i = 1 ; i <= n ; i++){
    for(int j = 1 ; j <= n ; j++){
      vis[j] = false;
      dist[j] = 0;
    }
    bfs(i);
  }
  cout << ans << endl;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5016 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 7 ms 5092 KB Output is correct
13 Correct 6 ms 5204 KB Output is correct
14 Correct 93 ms 5160 KB Output is correct
15 Correct 17 ms 5076 KB Output is correct
16 Correct 428 ms 5204 KB Output is correct
17 Correct 412 ms 5252 KB Output is correct
18 Correct 419 ms 5324 KB Output is correct