Submission #206376

#	Time	Username	Problem	Language	Result	Execution time	Memory
206376		theStaticMind	Bosses (BOI16_bosses)	C++14	100 / 100	836 ms	888 KiB

bosses

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 10000000000//0000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

vector<int> adj[5005];
vector<int> val(5005, INF);


void bfs(int s){


      val[s] = 1;
      queue<int> Q;
      Q.push(s);
      while(!Q.empty()){
            int x = Q.front();
            Q.pop();
            for(auto y : adj[x]){
                  if(val[y] > val[x] + 1){
                        Q.push(y);
                        val[y] = val[x] + 1;
                  }
            }
      }
}

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int n;
      cin >> n;
      for(int i = 1; i <= n; i++){
            int k;
            cin >> k;
            for(int j = 0; j < k; j++){
                  int x;
                  cin >> x;
                  adj[x].pb(i);
            }
      }
      int ans = INF;
      for(int i = 1; i <= n; i++){
            bfs(i);

            int cnt = 0;
            for(int j = 1; j <= n; j++){
                  cnt += val[j];
            }
            ans = min(ans, cnt);

            val = vector<int>(5005, INF);
      }
      cout << ans;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33