Submission #695205

#	Time	Username	Problem	Language	Result	Execution time	Memory
695205		Mr_Ph	Bosses (BOI16_bosses)	C++14	100 / 100	834 ms	740 KiB

bosses

///Never gonna give you up.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long long int lli;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
const ll mod=(ll)1e9+7;
const ll mod1=998244353;
///the defines :)
#define endl '\n'
#define vi vector<int>
#define vll vector<ll>
#define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i];
#define all(arr) arr.begin(),arr.end()
#define allr(arr) arr.rbegin(),arr.rend()
#define sz size()
///the end of the defines ;)
void bla()
{
  
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("notsus.txt","w",stdout);
#endif
}
int n;
vector<vector<int>>padj;
vector<vector<int>>adj;
vector<int>val;
bool valid=false;
void build(int node)
{
  for(int i=1;i<=n;i++)val[i]=1;
  vector<int>mp(n+1);
  queue<int>q;
  q.push(node);
  while(q.sz)
  {
    mp[q.front()]++;
    for(auto i:padj[q.front()])
    {
      if(!mp[i])
      {
        val[i]=val[q.front()]+1;
        mp[i]++;
         q.push(i);
      }
    }
    q.pop();
  }
  for(int i=1;i<=n;i++)
    if(!mp[i])valid=true;
}
int hello=0;
void preprocess(){}
void solve()
{
  cin>>n;
  padj.resize(n+1);
  adj.resize(n+1);
  val.resize(n+1);
  for(int i=0;i<n;i++)
  {
    int x;
    cin>>x;
    for(int j=0;j<x;j++)
    {
      int a;
      cin>>a;
      padj[a].push_back(i+1);
    }
  }
  int ans=INT_MAX;
  for(int i=1;i<=n;i++)
  {
    valid=false;
    build(i);
    if(valid)continue;
    hello=0;
   // dfs(i);
    for(int j=1;j<=n;j++)hello+=val[j];
    ans=min(ans,hello);
  }
  cout<<ans<<endl;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    preprocess();
  //  bla();
    int t=1;
   //cin>>t;
    while(t--)
        solve();
}

Compilation message (stderr)

bosses.cpp: In function 'void bla()':
bosses.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen("notsus.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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