Submission #969963

#	Time	Username	Problem	Language	Result	Execution time	Memory
969963		vjudge1	Bosses (BOI16_bosses)	C++17	0 / 100	173 ms	262144 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;
    vector<bool> visited(n+1,false); int cnt=0;
    vector<vector<int>> thisadj(n+1,vector<int>());

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

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