Submission #532936

#	Time	Username	Problem	Language	Result	Execution time	Memory
532936		kebine	Bosses (BOI16_bosses)	C++17	100 / 100	1166 ms	143888 KiB

bosses

#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 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33