Submission #720117

#	Time	Username	Problem	Language	Result	Execution time	Memory
720117		vjudge1	Bosses (BOI16_bosses)	C++17	67 / 100	1575 ms	1172 KiB

bosses

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

const int N=10001;
int n;
ll ans=LLONG_MAX;
ll sm;
int cnt;
vector<int>adj[N];
bool vis[N];

ll dfs(int u,vector<int>adj2[]){
  ll 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++){
    cnt=0;
    fill(vis+1,vis+n+1,false);
    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;
      cnt++;
      adj2[p].push_back(u);
      for(int v:adj[u]){
        if(!vis[v]){
          q.push({u,v});
        }
      }
    }
    if(cnt<n)continue;
    sm=0;
    ll x=dfs(i,adj2);
    ans=min(ans,sm);
  }
  cout << ans;

  return 0;
}

Compilation message (stderr)

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

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