제출 #720131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720131		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	1369 ms	1104 KiB

bosses

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

const int N=5001;
int n;
int ans=INT_MAX;
int sm;
int cnt;
vector<int>adj[N];
queue<pair<int,int>>q;
vector<int>adj2[N];
bool vis[N];

int dfs(int u){
  int sum=0;
  for(int v:adj2[u]){
    sum+=dfs(v);
  }
  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);
    for(int i=1; i<=n; i++)adj2[i].clear();
    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;
    int x=dfs(i);
    ans=min(ans,sm);
  }
  cout << ans;

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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