제출 #206371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
206371		theStaticMind	Bosses (BOI16_bosses)	C++14	22 / 100	7 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 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

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

void bfs_tree(int s){


      val[s] = 0;
      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;
                        tree[x].pb(y);
                  }
            }
      }
}

void dfs(int x){
      sub[x] = 1;
      for(auto y : tree[x]){
            dfs(y);
            sub[x] += sub[y];
      }
}

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_tree(i);

            for(int j = 1; j <= n; j++){
                  if(val[j] == INF)sub[j] = INF;
            }

            dfs(i);

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

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

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