Submission #969960

#	Time	Username	Problem	Language	Result	Execution time	Memory
969960		vjudge1	Bosses (BOI16_bosses)	C++17	67 / 100	1527 ms	1108 KiB

bosses

/*
 * With a little appreciation, in a mostly hollow tone, she says, "Delightful." As if the world has any meaning.
 * TASK : Bossa Nova
 * AUTHOR : Marszpace
*/

#include<bits/stdc++.h>
using namespace std;

pair<int,int> dfs(vector<vector<int>>& adj, int u){
  int res1=0,res2=0;
  for(auto v:adj[u]){
    auto p=dfs(adj,v);
    res1+=p.first;
    res2+=p.second;
  }
  return {res1+res2+1,res2+1};
}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> adj(n+1,vector<int>());
  for(int i=1;i<=n;i++){
    int k;
    cin >> k;
    for(int j=0;j<k;j++){
      int v;
      cin >> v;
      adj[v].push_back(i);
    }
  }

  int res=INT_MAX;
  for(int root=1;root<=n;root++){
    queue<pair<int,int>> bfs;
    bfs.push({root,0});
    vector<bool> visited(n+1,false);
    int cnt=0;
    vector<vector<int>> thisadj(n+1,vector<int>());
    while(!bfs.empty()){
      auto [u,p]=bfs.front();bfs.pop();
      if(visited[u]){continue;}
      visited[u]=true;cnt++;
      if(p!=0){
        thisadj[p].push_back(u);
      }
      for(auto v:adj[u]){
        bfs.push({v,u});
      }
    }
    if(cnt==n){
      res=min(res,dfs(thisadj,root).first);
    }
  }
  cout << res;
  return 0;
}

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