Submission #720094

#	Time	Username	Problem	Language	Result	Execution time	Memory
720094		vjudge1	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	796 KiB

bosses

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

const int N=10001;
int n;
int ans=INT_MAX;
int sm;
vector<int>adj[N];
bool vis[N];
int val[N];

int dfs(int u,vector<int>adj2[]){
  int sum=0;
  for(int v:adj2[u]){
    sum+=dfs(v,adj2);
  }
  sm+=sum+1;
  return sum+1;
}

int main(){
  ios_base::sync_with_stdio(0),cin.tie(0);
  cin >> n;
  for(int i=1; i<=n; i++){
    int m;
    cin >> m;
    for(int j=1; j<=m; j++){
      int v;
      cin >> v;
      adj[v].push_back(i);
    }
  }
  for(int i=1; i<=n; i++){
    fill(vis+1,vis+n+1,false);
    fill(val+1,val+n+1,0);
    vector<int>adj2[N];
    queue<pair<int,int>>q;
    q.push({0,i});
    while(!q.empty()){
      int u=q.front().second;
      int p=q.front().first;
      q.pop();
      if(vis[u])continue;
      vis[u]=true;
      adj2[p].push_back(u);
      for(int v:adj[u]){
        if(!vis[v]){
          q.push({u,v});
        }
      }
    }
    int x=dfs(i,adj2);
    ans=min(ans,sm);
  }
  cout << ans;

  return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:52:9: warning: unused variable 'x' [-Wunused-variable]
   52 |     int x=dfs(i,adj2);
      |         ^

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