Submission #1090996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090996		owieczka	Bosses (BOI16_bosses)	C++17	0 / 100	0 ms	348 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;
}

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);
      }
   }
   for (int i = 1; i <= n; i++)
   {
      m = min(bfs(i), m);
   }
   cout << m << '\n';
}

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