제출 #1091267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1091267		owieczka	Bosses (BOI16_bosses)	C++17	100 / 100	584 ms	3820 KiB

bosses

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

bitset<5'001> o[5001];
ll odl [5001];
vector<int> g[5'001];
queue<pair<int, int>> qu;


ll bfs(int it)
{
   qu.push({it, 0});
   odl[it] = 1;
   ll w = 0;
   while (!qu.empty())
   {
      auto v = qu.front();
      qu.pop();
      if (o[it][v.first])continue;
      o[it][v.first] = 1;
      odl[v.first] = odl[v.second] + 1;
      w += odl[v.first];
      for (auto i : g[v.first])
      {
         if (!o[it][i])qu.push({i, v.first});
      }
   }
   return w;
}
bitset<5'001> prawda;

int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   int n, a, b;
   ll m = LLONG_MAX;
   cin >> n;
   for (int i = 1; i <= n; i++)
   {
      cin >> a;
      while (a--)
      {
         cin >> b;
         g[b].push_back(i);
      }
      prawda[i] = 1;
   }
   for (int i = 1; i <= n; i++)
   {
      //m = min(bfs(i), m);
      auto sk = bfs(i);
      if (o[i] == prawda)m = min(sk, m);
   }
   cout << m << '\n';
}

/*

*/

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