oj.uz

Submission #532936

# Submission time Handle Problem Language Result Execution time Memory
532936 2022-03-04T08:54:00 Z kebine Bosses (BOI16_bosses) C++17
100 / 100
 1166 ms 143888 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> vec[5005];
vector<int> temp[5005];
int salary[5005];

long long bfs(int x) {
  queue<int> q;
  q.push(x);
  int visited[n+1];
  memset(visited, -1, sizeof(visited));
  visited[x] = 1;
  int fre = 1;
  

  while(!q.empty()) {
    int a = q.front(); q.pop();

    for(auto v: vec[a]) {
      if(visited[v] == -1) {
        temp[a].push_back(v);
        fre++;
        visited[v] = visited[a]+1;
        
        q.push(v);
      }
    }
  }
  if(fre != n) {
    return LLONG_MAX;
  }
  else {
    long long total1 = 0;
    for(int i= 1; i<=n; i++) {
      total1 += visited[i];
    }
    return total1;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;

  for(int i = 1; i<=n; i++) {
    int a;
    cin >> a;
    for(int ii = 1; ii<=a; ii++) {
      int b;
      cin >> b;
      vec[b].push_back(i);
    }
  }

  long long min1 = LLONG_MAX;

  for(int i = 1; i<=n; i++) {
    min1 = min(min1, bfs(i));
  }

  cout << min1 << endl;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 560 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 560 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 3 ms 716 KB Output is correct
14 Correct 240 ms 40364 KB Output is correct
15 Correct 9 ms 972 KB Output is correct
16 Correct 754 ms 89828 KB Output is correct
17 Correct 1166 ms 143240 KB Output is correct
18 Correct 1150 ms 143888 KB Output is correct